#include <bits/stdc++.h>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, m;

void Dijkstra (int node, vector < vector < pair < int , int > > > &g, vector < int > &dist){
  priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > q;
  vector < bool > visited(n, false);
  q.push({0, node});
  dist[node] = 0;
  visited[node] = true;
  while(!q.empty()){
    node = q.top().second;
    q.pop();
    visited[node] = false;
    for(int i = 0; i < g[node].size(); i++){
      int v = g[node][i].first;
      int weight = g[node][i].second;
      if(dist[v] > dist[node] + weight){
        dist[v] = dist[node] + weight;
        if(visited[v]){
          continue;
        }
        visited[v] = true;
        q.push({dist[v], v});
      }
    }
  }
}

int main(){
  in>>n>>m;
  vector < vector < pair < int , int > > > g(n + 1);
  vector < int > dist(n + 1, INT_MAX);
  while (m--) {
    int x, y, cost;
    in>>x>>y>>cost;
    g[x].push_back({y, cost});
  }

  Dijkstra(1, g, dist);

  for(int i = 2; i <= n; i++)
    out<<(dist[i] == INT_MAX ? 0 : dist[i])<<" ";
}