#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
const int Nmax = 50444;
const int INF = 0x3f3f3f3f;
int N, M, d[Nmax];
char vis[Nmax];
vector<pii> G[Nmax];
int main(void) {
  fin >> N >> M;
  int a,b,c;
  rep(i, M) {
    fin >> a >> b >> c;
    --a,--b;
    G[a].push_back({b,c});
  }
  rep(i,N){d[i]= INF;}
  priority_queue<pii, vector<pii>, greater<pii> > Q;
  Q.push({0, 0});
  while(!Q.empty()) {
    pii X = Q.top(); Q.pop();
    int dist = X.first;
    int nod = X.second;
    if (vis[nod])
      continue;

    d[nod] = dist;
    vis[nod] = 1;

    for(auto Y: G[nod]) {
      if (d[nod] + Y.second < d[Y.first]) {
        Q.push({d[nod] + Y.second, Y.first});
      }
    }
  }
  repa(i,1,N) {
    fout << (d[i] == INF ? 0 : d[i]) << ' ';
  }
  fout << endl;
  return 0;
}