#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector < pair < int, int > > v[nmax];
priority_queue < pair < int,int > > q;
int dist[nmax], n, m;
bool viz[nmax];
void read()
{
     in >> n >> m;
     int a,b,c;
     while ( m--)
     {
          in >> a >> b >> c;
          v[a].push_back({b,c});
     }
     for(int i=2; i<=n; i++)
          dist[i] = INT_MAX;
}
void dijkstra()
{
     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();
     dijkstra();
     for(int i=2; i<=n; i++)
          (dist[i]==INT_MAX) ? out << 0 <<' ' : out << dist[i] <<' ';

    return 0;
}