#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector < pair< int, int > > v[nmax];
int n,m,dist[nmax];
bool processed[nmax];
priority_queue< pair < int,int > > q;
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=1; i<=n; i++)
          dist[i] = 1<<30;
}
void djk()
{
     q.push({0,1});
     dist[1]=0;
     while(!q.empty())
     {
         int head = q.top().second;
          q.pop();
          if( processed[head] ) continue;
          processed[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 << 0 <<' ' : out << dist[i] <<' ';

    return 0;
}