#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF (INT_MAX/2)
using namespace std;
int G[101][101];
int w[101];
int visited[101];
int n, m;
void Dijkstra();
int main()
{
int a, b, c, i, j;
while (scanf("%d %d", &n, &m) && (n || m))
{
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
{
G[i][j] = i == j ? 0 : INF;
}
for (i = 0; i < m; i++)
{
scanf("%d %d %d", &a, &b, &c);
if (G[a][b] > c)
G[a][b] = G[b][a] = c;
}
Dijkstra();
printf("%dn", w[n]);
}
return 0;
}
void Dijkstra()
{
memset(visited, 0, sizeof(visited));
for (int i = 1; i <= n; i++)
w[i] = G[1][i];
w[1] = 0;
for (int i = 1; i <= n; i++)
{
int min = INF;
int Vmin;
for (int j = 1; j <= n; j++)
{
if (!visited[j] && w[j] < min&&i != j)
{
min = w[Vmin = j];
}
}
visited[Vmin] = 1;
for (int j = 1; j <= n; j++)
{
if (w[j] > w[Vmin] + G[Vmin][j])
w[j] = w[Vmin] + G[Vmin][j];
}
}
}
近期评论