#include <bits/stdc++.h>
#define pp pair<int,int>
#define cost first
#define nod second
#define inf 0x3f3f3f3f
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
priority_queue <pp,vector<pp>,greater<pp>> q;
vector <pp> v[50001];
int dp[50001];
int main () {
  int n,m;
  f >> n >> m;
  for(int i=1; i<=m; i++) {
    int x,y,c;
    f >> x >> y >> c;
    v[x].push_back({c,y});
  }
  for(int i=1; i<=n; i++) dp[i] = inf;
  dp[1] = 0;
  q.push({0,1});
  while(q.size()) {
    int nod = q.top().nod;
    int cost = q.top().cost;
    q.pop();
    if(dp[nod]!=cost)
      continue;
    for(int i=0; i<v[nod].size(); i++) {
      pp vecin = v[nod][i];
      if(dp[vecin.nod] > cost + vecin.cost) {
        q.push({cost + vecin.cost,vecin.nod});
        dp[vecin.nod] = cost + vecin.cost;
      }
    }
  }
  for(int i=1; i<=n; i++) g << dp[i] << " ";
  return 0;
}