#include
#define Infinite 10000000
int number_points, number_ways;
int buffer_consume[110][110];
int dist[110];
bool discovered[110];
int getMinIndex()
{
int min_value = Infinite;
int min_index = 0;
for (int i = 1; i <= number_points; i++)
{
if (discovered[i] == false && dist[i] <= min_value)
{
min_value = dist[i];
min_index = i;
}
}
return min_index;
};
void dijkstra()
{
for (int i = 1; i <= number_points; i++)
{
dist[i] = buffer_consume[1][i];
discovered[i] = false;
}
dist[1] = 0;
discovered[1] = true;
for (int count = 1; count != number_points; count++)
{
int u = getMinIndex();
discovered[u] = true;
if (u == number_points)
return;
for (int v = 1; v <= number_points; v++)
{
if (dist[u] + buffer_consume[u][v] < dist[v])
dist[v] = dist[u] + buffer_consume[u][v];
}
}
}
int main()
{
scanf("%d%d", &number_points, &number_ways);
while(number_points != 0 && number_ways != 0)
{
for (int x = 1; x <= number_points; x++)
for (int y = 1; y <= number_points; y++)
{
buffer_consume[x][y] = Infinite;
}
for (int i = 0; i < number_ways; i++)
{
int x, y, consume;
scanf("%d%d%d", &x, &y, &consume);
buffer_consume[x][y] = consume;
buffer_consume[y][x] = consume;
}
dijkstra();
printf("%d\n", dist[number_points]);
scanf("%d%d", &number_points, &number_ways);
}
return 0;
}
京公网安备 11010802041100号