#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector < pair < int, int > > v[nmax];
bitset < nmax > viz;
priority_queue < pair < int , int > > q;
int dist[nmax];
int n,m;
void read()
{
     in >> n  >> m;
     int a,b,c;
     for(int i=1; i<=m; i++)
     {
          in >> a >> b >> c;
          v[a].push_back({b,c});
     }
     for( int i=2; i<=n; i++)
          dist[i] = 1 << 30;
}
void djk()
{
     q.push({0,1});
     while( !q.empty() )
     {
          int head = q.top().second;
          q.pop();
          if( viz[head] ) continue;
          viz[head] = 1;
          for(int i=0; i<v[head].size(); i++ )
          {
               int j = v[head][i].first;
               int cost = v[head][i].second;
               if( dist[j] > dist[head] + cost )
               {
                    dist[j] = dist[head] + cost;
                    q.push({-dist[j], j});
               }
          }
     }
}
int main()
{
     read();
     djk();
     for(int i=2; i<=n; i++)
          ( dist[i] != 1 << 30 ) ? out << dist[i] << ' ' : out << 0 << ' ';


    return 0;
}