#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define INF 0x3f3f3f3f
#define size 50100
long n,m,i,u,x,y,t;
long dist[size];

struct nod{
 long csp,ta;
};

vector<nod> v[size];
vector<nod>::iterator q;
nod adat;

int main()
{
 ifstream in("bellmanford.in");
 ofstream out("bellmanford.out");

 in >> n >> m;
 for(i=1;i<=m;++i){
   in >> x >> y >> t;
   adat.csp=y;
   adat.ta=t;
   v[x].push_back(adat);
 }

 queue<long> heap;

// memset(dist,INF,sizeof(dist));
 for(i=1;i<=n;++i) dist[i]=INF;
 dist[1]=0;
 heap.push(1);

 while(!heap.empty()){
  u=heap.front();
  heap.pop();
  for(q=v[u].begin(); q<v[u].end(); ++q)
   if(dist[q->csp]>dist[u]+q->ta)
   {
      dist[q->csp]=dist[u]+q->ta;
      heap.push(q->csp);
   }
 }

 for(i=2;i<=n;++i)
    if(dist[i]==INF) out << "0 ";
    else out << dist[i] << " ";

 return 0;
}