#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct VECIN{
  int v, m;
};
struct COST{
  int nod, c;
  bool operator < (const COST &other) const {
    return (c != other.c) ? (c > other.c) : (nod > other.nod);
  }
};
vector<VECIN>v[50005];
priority_queue<COST>q;
bool viz[50005];
int cost[50005];
int main(){
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  int n, m, u, i;
  VECIN x;
  COST a, b;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i ++){
    scanf("%d%d%d", &u, &x.v, &x.m);
    v[u].push_back(x);
  }
  a.nod = 1;
  a.c = 0;
  q.push(a);
  while (!q.empty()){
    a = q.top();
    q.pop();
    if (viz[a.nod] == true)
      continue;
    cost[a.nod] = a.c;
    viz[a.nod] = true;
    for (i = 0; i < v[a.nod].size(); i ++){
      if (viz[v[a.nod][i].v] == false){
        b.nod = v[a.nod][i].v;
        b.c = a.c + v[a.nod][i].m;
        q.push(b);
      }
    }
  }
  for (i = 2; i <= n; i ++)
    printf("%d ", cost[i]);
  return 0;
}