#include <iostream>  #include <cstring>  #include <queue>    using namespace std;  const int maxn=120;  const int maxm=10010;  const int INF=999999;//如果在算法中没有先判断是不是<inf，就直接加的话，如果INF过大就可能造成溢出  int dis[maxn];//起点到每个点的花费  int visted[maxn];//该点是否在队列中  int head[maxn];//head[i]记录第i个点最后出发的边的编号,用于代入edge[i].next,使edge[head[i]].next==边号，即第i个点的上一条边的编号，直到当该编号等于-1时说明从这个点出发的所有的边已都被遍历一遍  int len;//当前边的边号  struct Edge{      //用e[].next还有一个好处，就是不用建立邻接表使每个点到每个点都有距离，就不用将在题目中没有说明的距离赋值为无穷大      int nxet;//从该边的出发节点出发的，上一条边，如2号点可以出发3号点构成a边，2号点还可以出发到4号点构成b边，那么e[b].next==a，这是SPFA有序搜索提高效率的地方，就是每次只是更新通过从队首拿出的点的出发的所有边所直接到达（中间不再经过其他点）的点,然后如果新到达的点被更新（松弛操作成功）那么就将被更新的点重新放入队列。记录从一个点出发的所有边的结构就是这个链表      int to;//该边的到达节点      int cost;//该边的花费  }edge[maxm];  //struct node{};如uva11280，放入队列中的点，编号和停留次数不同都代表不同  void add(int from,int to,int cost){      edge[len].to=to;      edge[len].cost=cost;      edge[len].nxet=head[from];      head[from]=len;      len++;  }  void SPFA(int s){      queue <int > q;      q.push(s);      visted[s]=1;        while(!q.empty()){          int cur=q.front();          q.pop();          visted[cur]=0;          for(int i=head[cur];i!=-1;i=edge[i].nxet){                  if(dis[edge[i].to]>dis[cur]+edge[i].cost){                      dis[edge[i].to]=dis[cur]+edge[i].cost;                      if(!visted[edge[i].to]){                          visted[edge[i].to]=1;                          q.push(edge[i].to);                      }                  }          }      }  }  int main()  {      int n,m;      while(cin>>n>>m&&n!=0){          len=1;          int a,b,c;          memset(visted,0,sizeof(visted));          memset(head,-1,sizeof(head));          for(int i=1;i<=m;i++){              cin>>a>>b>>c;              add(a,b,c);              add(b,a,c);          }          for(int i=1;i<=n;i++){              dis[i]=INF;          }          int s=1;//起点          dis[s]=0;//这是关键，确定哪个点作为源点，使这个dis数组内的其他值为从此点出发到达其他点最短的距离。          SPFA(s);          cout<<dis[n]<<endl;      }      return 0;  }