#include "bits/stdc++.h"

using namespace std;


const int INF = 1000000003;
const int NMax = 50005;

struct Node{
  int dist;
  int node;
  bool operator<(const Node &x) const{
    return (dist > x.dist);
  }
};

int n,m,x,y,c;
int d[NMax];
vector<pair<int,int> > G[NMax];

int main(){
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");

  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    cin >> x >> y >> c;
    G[x].push_back({y,c});
  }
  for(int i = 1; i <= n; ++i){
    d[i] = INF;
  }
  d[1] = 0;
  priority_queue<Node> pq;
  pq.push({0, 1});
  while(!pq.empty()){
    int dist = pq.top().dist;
    int node = pq.top().node;
    pq.pop();
    if(dist > d[node])
      continue;
    for(int i = 0; i < G[node].size(); ++i){
      if(d[G[node][i].first] > d[node] + G[node][i].second){
        d[G[node][i].first] = d[node] + G[node][i].second;
        pq.push({d[G[node][i].first], G[node][i].first});
      }
    }
  }
  for(int i = 2; i <= n; ++i){
    if(d[i] == INF){
      cout << 0 << ' ';
      continue;
    }
    cout << d[i] << ' ';
  }
}