#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <functional>
#include <queue>

#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

const int kinf = 50000000;

vector<pair<int, int> > graph[50005];
int dist[50005], taken[50005];

int main(){
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  memset(dist, 1337, sizeof(dist));

  int n, m;
  scanf("%d%d", &n, &m);
  dist[1] = 0;

  for(int i = 1; i <= m; ++i){
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    graph[x].pb(mp(y, c));
  }

  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > h;
  h.push(mp(0, 1));

  while(!h.empty()){
    pair<int, int> now = h.top();
    h.pop();

    if(taken[now.s])
      continue;

    dist[now.s] = now.f;
    taken[now.s] = 1;

    for(int i = 0; i < graph[now.s].size(); ++i) if(!taken[graph[now.s][i].f])
      if(graph[now.s][i].s + dist[now.s] < dist[graph[now.s][i].f]){
        h.push(mp(graph[now.s][i].s + dist[now.s], graph[now.s][i].f));
        dist[graph[now.s][i].f] = graph[now.s][i].s + dist[now.s];
      }
  }

  for(int i = 2; i <= n; ++i)
    if(dist[i] <= kinf)
      printf("%d ", dist[i]);
    else
      printf("0 ");

  return 0;
}