#include <bits/stdc++.h>
#define MAXN 50000
using namespace std;
vector<pair<int,int>>g[MAXN + 1];
int dist[MAXN + 1];
// pereche (muchie, cost)
priority_queue <pair<int, int>> pq;

int main(){
  FILE *fin, *fout;
  int n, m, u, v, w, i  ;
  fin = fopen( "dijkstra.in", "r" );

  fscanf(fin, "%d%d", &n, &m);
  for( i = 1; i <= m; i++ ){
    fscanf(fin, "%d%d%d", &u, &v, &w);
    g[u].push_back({v, w});
  }

  fclose( fin );
  fout = fopen( "dijkstra.out", "w" );

  for( i = 2; i <= n; i++ )
    dist[i] = -1;
  dist[0] = 1;
  pq.push({0, 1});
  while(!pq.empty()){
    pair<int, int> current = pq.top();
    pq.pop();
    int d = -current.first;
    int node = current.second;
    if(d == dist[node]){
      for(auto &edge : g[node]){
        int newnode = edge.first;
        int newcost = edge.second + dist[node];
        if(dist[newnode] < 0 || dist[newnode] > newcost){
          dist[newnode] = newcost;
          pq.push({-newcost, newnode});
        }
      }
    }
  }
  for( i = 2; i <= n; i++ ){
    dist[i] = max(dist[i], 0);
    fprintf(fout, "%d ", dist[i]);
  }

  fclose( fout );
  return 0;
}