问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入
3 3
1 2 -1
2 3 -1
3 1 2

样例输出
-1
-2

数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

#include 
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define MAXINT 100000000 #define N 20001 using namespace std; struct eg{ int e; int w; }; int p[N]; bool flag[N]; vector
        
          v[N]; int plint[N]; vector
         
           pl; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ p[i] = MAXINT; } for(int i=1;i<=m;i++){ int t1,t2,t3; eg ve; scanf("%d%d%d",&t1,&t2,&t3); ve.e = t2; ve.w = t3; v[t1].push_back(ve); if(t1==1){ p[t2] = t3; pl.push_back(t3); plint[pl.size()] = t2; } } for(int i=2;i<=n;i++){ int minN = MAXINT; int tt = 0; int index = 0; vector
          
           ::iterator iteri = pl.begin(); vector
           
            ::iterator rem; for(int j=0;iteri!=pl.end();iteri++,j++){ int tint = *iteri; if(tint
            
             ::iterator iter = v[tt].begin(); while(iter!=v[tt].end()){ int ee = iter->e; int ww = iter->w; if(p[ee]==MAXINT){ p[ee] = p[tt]+ww; pl.push_back(p[ee]); plint[pl.size()] = ee; } else if(p[ee]>p[tt]+ww){ int k; for(k=1;k<=pl.size();k++){ if(p[k]==ee) break; } p[ee] = p[tt]+ww; pl[k] = p[ee]; } iter++; } } for(int i=2;i<=n;i++){ printf("%d\n",p[i]); } return 0; }