#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,d[50005],x,g[50005],c;
struct nod{int nd,val;}p;
vector <nod>v[50005];
queue <int>C;
int main()
{fin>>n>>m;
 for(i=1;i<=m;i++)
    {fin>>x>>p.nd>>p.val;
     v[x].push_back(p);
     g[x]++;
    }
 C.push(1);
 for(i=1;i<=n;i++)
    d[i]=1000000000;
    d[1]=0;
 while(C.size()>0)
   {c=C.front();
    C.pop();
    for(i=0;i<g[c];i++)
       {if(v[c][i].val+d[c]<d[v[c][i].nd]){d[v[c][i].nd]=v[c][i].val+d[c];
                                           C.push(v[c][i].nd);
                                          }
       }
   }
for(i=2;i<=n;i++)
   {if(d[i]==1000000000)fout<<"0 ";
       else fout<<d[i]<<" ";
   }
}