#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(int last) {
  priority_queue<Node, vector<Node>, greater<Node> > pq;
  dist[last] = 0; //ai adaugat un nod in multime;
  pq.push({last, dist[last]});
  while(0 < pq.size()) {
    int last = pq.top().index;
    pq.pop();
    if(used[last] == 0) {
      used[last] = 1;
      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]});
        }
      }
    }
  }
}

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(1);
  for(int i = 2 ; i <= n ;i++){
        if(dist[i] != inf)
      out<<dist[i]<<" ";
      else
            out<<"0 ";
  }
}