#include <fstream>
#include <vector>
using namespace std;
#define nod first
#define cost second
const int NMAX=50001;
const int Inf=1000000000;
vector< pair<int,int> > G[NMAX];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N,M,d[NMAX];
int h[NMAX],p[NMAX],nrH;     
void Sift(int k){
     int Son;
     if (2*k<=nrH){
       Son=2*k;
       if (Son+1<=nrH && d[h[Son+1]]<d[h[Son]]) ++Son;
       if (d[h[Son]]>=d[h[k]]) Son=0;
       }else Son=0;
     while (Son){
       p[h[k]]=Son;p[h[Son]]=k;
       int w=h[k];h[k]=h[Son];h[Son]=w;
       k=Son;
       if (2*k<=nrH){
       Son=2*k;
       if (Son+1<=nrH && d[h[Son+1]]<d[h[Son]]) ++Son;
       if (d[h[Son]]>=d[h[k]]) Son=0;
       }else Son=0;
       }
     }
void Percolate(int k){
     if (k>nrH) return;
     int key=h[k];
     while (k>1 && d[key]<d[h[k/2]]){
           p[h[k/2]]=k;
           h[k]=h[k/2];
           k/=2;}
     h[k]=key;
     p[key]=k;
     }
void add(int i){
     h[++nrH]=i;
     p[i]=nrH;
     Percolate(nrH);
     }
int Extract_Min(){
    int x=h[1];
    p[x]=nrH;
    h[1]=h[nrH--];
    p[h[1]]=1;
    Sift(1);
    return x;
    }
void Dijkstra(){
     int x;
     vector< pair<int,int> >::iterator it;
     for (x=1;x<=N;++x) d[x]=Inf;
     d[1]=0;
     for (x=1;x<=N;++x) add(x);
     
     while (nrH>0){
       x=Extract_Min();
       for (it=G[x].begin();it!=G[x].end();++it)
         if (d[it->nod]>d[x]+it->cost){
          d[it->nod]=d[x]+it->cost;
          Percolate(p[it->nod]);}
       }
     for (x=2;x<=N;++x) {
         if (d[x]==Inf) d[x]=0;
         g<<d[x]<<' ';}
     }
int main(){
    int i,j,k;
    f>>N>>M;
    while (M--){
     f>>i>>j>>k;
     G[i].push_back(make_pair(j,k));
     }
    Dijkstra();
    return 0;
}