#include <cstdio>
#include <queue>
#include <vector>
#define Nmax 50099
#define oo 2000000000
using namespace std;

int N,M,ante[Nmax],d[Nmax];
struct edge{int y,c;} aux;
vector < edge > G[Nmax];

struct cmp
{
     bool operator()(const int &a,const int &b)const
     {
          return d[a]>d[b];
     };
};

priority_queue < int , vector <  int > , cmp > pq;


void Dijkstra(int S)
{
     for(int i=1;i<=N;++i)d[i]=ante[i]=oo;
     d[S]=0; ante[S]=S;
     for( pq.push(S); !pq.empty() ; pq.pop())
     {
          int node=pq.top();
          for(vector < edge > ::iterator it=G[node].begin();it!=G[node].end();++it)
               if(d[node]+it->c<d[it->y])
               {
                    d[it->y]=d[node]+it->c;
                    pq.push(it->y);
               }
     }

     for(int i=1;i<=N;++i)
          if(d[i]==oo)d[i]=ante[i]=0;
}
int main()
{
     freopen("dijkstra.in","r",stdin);
     freopen("dijkstra.out","w",stdout);
     scanf("%d %d",&N,&M);
     for(int i=1;i<=M;++i)
     {
          edge aux;
          int x;
          scanf("%d %d %d",&x,&aux.y,&aux.c);
          G[x].push_back(aux);
     }
     Dijkstra(1);
     for(int i=2;i<=N;++i)
          printf("%d ",d[i]);
     printf("\n");
     return 0;
}