#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<utility>
#include<bitset>
 
#define INF 1<<30
#define NMAX 50005
#define TYPE pair<int,int>
 
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
 
using namespace std;
 
vector<pair <int,int> >G[NMAX];
vector<int>::iterator it;
int n,m,dist[NMAX];
priority_queue<TYPE,vector<TYPE>,greater<TYPE> > HEAP;
bool used[NMAX];
 
void read( void )
{
    fscanf(f,"%d%d",&n,&m);
 
    for(int i(1); i <=m ; ++i )
    {
        int a,b,c;
        fscanf(f,"%d%d%d",&a,&b,&c);
        G[a].push_back(make_pair(b,c));
    }
    fclose(f);
 
}
void solve( void )
{
    for(int i(1); i<=n ; dist[i++]=INF)
 
  dist[1]=0;
  HEAP.push(make_pair(0,1));
 
  while(!HEAP.empty())
  {
      int node=HEAP.top().second;
      HEAP.pop();
 
 
      for(int i(0); i <G[node].size(); ++i )
      {
       int newnode=G[node][i].first;
       int dis=G[node][i].second;
       if( dist[newnode] > dist[node]+dis)
          {
              dist[newnode]=dist[node]+dis;
              HEAP.push(make_pair(dist[newnode],newnode));
          }
 
      }
 
  }
 
 
}
void write( void )
{
    for(int i(2); i <=n; ++i )
        if(dist[i]!=INF)
        fprintf(g,"%d ",dist[i]);
        else
        fprintf(g,"0 ");
    fclose(g);
}
 
 
int main( void )
{
    read();
    solve();
    write();
    return 0;
}