#include <fstream>
#include <utility>
#include <vector>
#define inf 1000000000
using namespace std;

ifstream in; ofstream out;
vector <pair <long,short> > data[50001];
pair <long,short> t; long N,M,Nh;
long dist[50001],heap[50001],ind[50001];

void swap (long x, long y) {
     long z=heap[x]; heap[x]=heap[y]; heap[y]=z;
     ind[heap[x]]=x; ind[heap[y]]=y;
}

void upheap (long x) {
     long z=x;
     while ((z>1)&&(dist[heap[z/2]]>dist[heap[z]])) {
           swap (z,z/2);
           z/=2;
     }
}

void downheap (long x) {
     long y=1,z=x;
     while (y) {
           y=0;
           if (2*z<=Nh) {
              y=2*z;
              if (2*z+1<=Nh) if (dist[heap[2*z+1]]<dist[heap[y]]) y=2*z+1;
           }
           if (dist[heap[z]]<dist[heap[y]]) y=0;
           if (y) swap (y,z);
           z=y;
     }
}

int main () {
    in.open ("dijkstra.in"); out.open ("dijkstra.out");
    long i,j;
    in>>N>>M;
    for (i=1; i<=M; i++) {
        in>>j>>t.first>>t.second;
        data[j].push_back (t);
    }
    dist[1]=0; heap[1]=1; ind[1]=1; Nh=N;
    for (i=2; i<=N; i++) {
        dist[i]=inf;
        heap[i]=i;
        ind[i]=i;
    }
    while (Nh) {
          i=heap[1];
          if (dist[i]==inf) break;
          swap (1,Nh); Nh-=1; downheap (1);
          for (j=0; j<data[i].size (); j++) {
              t=data[i].at (j);
              if (ind[t.first]<=Nh)
                 if (dist[i]+t.second<dist[t.first]) {
                    dist[t.first]=dist[i]+t.second;
                    upheap (ind[t.first]);
                 }
          }
    }
    for (i=2; i<=N; i++)
        if (dist[i]==inf) out<<0<<" ";
        else out<<dist[i]<<" ";
    out<<"\n";
    in.close (); out.close ();
    return 0;
}