#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int INF=0x3f3f3f3f;
vector<pair<int,int> > noduri[50001];
vector<pair<int,int> >::iterator it;
priority_queue <pair<int,int> > q;
int n,m,x,y,c,i;
int main()
{
     fin>>n>>m;
     for(int i=1;i<=m;++i)
     {
         fin>>x>>y>>c;
         noduri[x].push_back(make_pair(c,y));
     }
 vector<int>d(n+1,INF);
 int val,nod,N,V;
 d[1]=0;
 for(q.push(make_pair(-d[1],1));!q.empty();)
 {
     val=-q.top().first;
     nod=q.top().second;
     q.pop();
     if(d[nod]<val)
        continue;
     for(it=noduri[nod].begin();it!=noduri[nod].end();++it)
     {
         V=(*it).second;
         N=(*it).first;
         if(d[V]>d[nod]+N){
            d[V]=d[nod]+N;
            q.push(make_pair(-d[V],V));
         }
     }
 }
 for(i=2;i<=n;++i)
    if(d[i]!=INF)
    fout<<d[i]<<" ";
    else
        fout<<0<<" ";
 return 0;
}