Dijkstra算法的核心思想就是两步排序，一个是对于一个点而言，他的最小边要经过所有其他点最小边的测试才能确认，也就是说要在这其中找一个最大的边出来；第二个是对于每次循环而言的，每次的更新d数组都是为了要选出最短的距离。

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#define INF 65535

using namespace std;

typedef pair<int,int> Node;

int n,m;

int G[][];

bool operator < (Node a,Node b)

{

 return a.first > b.first;

}

int Dijkstra()

{

 int v,min;

 int d[];

 int vis[];

 priority_queue<Node> q;

 memset(vis,,sizeof(vis));

 for(int i = ;i <= n;i++)

  d[i] = INF;

 d[] = ;

 q.push(make_pair(d[],));

 while(!q.empty()) {

  Node t = q.top();

  q.pop();

  if(vis[t.second])

   continue;

  vis[t.second] = ;

  for(int i = ;i <= n;i++)

   if(!vis[i] && d[i] > t.first+G[t.second][i]) {

    d[i] = t.first+G[t.second][i];

    q.push(make_pair(d[i],i));

   }

 }

 return d[n];

}

int main()

{

 int x,y,w;

 while(~scanf("%d%d",&n,&m))

 {

  if(!n && !m) break;

  for(int i = ;i <= n;i++)

   for(int j = ;j <= n;j++)

    G[i][j] = i==j?:INF;

  for(int i = ;i <= m;i++) {

   scanf("%d%d%d",&x,&y,&w);

   if(w < G[x][y])

    G[x][y] = G[y][x] = w;

  }

  printf("%d\n",Dijkstra());

 }

 return ;

}