#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

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

int const nmax = 50000;
int const inf = INT_MAX;

struct Edge{
  int to;
  int cost;
};

vector<Edge> g[1 + nmax];
int used[5 + nmax];
int dist[5 + nmax];
struct Node {
  int index;
  int d;

  bool operator > (Node a ) const {
    return d > a.d;
  }
};

void dijkstra() {
  priority_queue<Node, vector<Node>, greater<Node> > pq;
  int last;
  last = 1;
  dist[last] = 0; //ai adaugat un nod in multime;
  used[1] = 1;

  while(true){
    for(int i = 0; i < g[last].size(); i++) {
       Edge &e = g[last][i];
      if(dist[last] + e.cost < dist[e.to]){
        dist[e.to] = dist[last] + e.cost;
        pq.push({e.to , dist[e.to]});
      }
    }
    while(0 < pq.size() && used[pq.top().index] == 1){
      pq.pop();
    }
    if(pq.size() == 0)
      break;
    int node = pq.top().index;
    pq.pop();
    last = node;
    used[node] = 1;
  }
}

int main(){
  int n, m;
  in >> n >> m;
  for(int i = 1 ; i <= m ;i++){
    int a, b, c;
    in >> a >> b >> c;
    g[a].push_back({b , c});
  }
  for(int i = 1 ; i <= n ;i++){
    dist[i] = inf;
  }
  dijkstra();
  for(int i = 2 ; i <= n ;i++){
		if(dist[i] == inf)
      out<<dist[i]<<" ";
	  else
			out<<"0 ";
  }
}