#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <bitset>
#include <utility>

#define rep(i,a,b) for(int i=int(a); i<=int(b); ++i)
#define rev(i,b,a) for(int i=int(b); i>=int(a); --i)
#define rec(i,a,b,c) for(int i=int(a); i<=int(b); i+=int(c))
#define recv(i,a,b,c) for(int i=int(a); i>=int(b); i-=int(c))
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back(x)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(auto it=(container).begin(); it != (container).end(); ++it)
#define sqr(x) ((x)*(x))
#define sz(a) int((a).size())
#define mod(a,n) ((a) < 0 ? ((n)+(a)) : ((a)%(n)))
#define mout(M,n,m) rep(i,0,(n)-1){ rep(j,0,(m)-1) cout << (M)[i][j] << " ";  cout << "\n"; }
using namespace std;

#define INF_ULL ULLONG_MAX
#define INF_LL  LLONG_MAX
#define NINF_LL LLONG_MIN
#define INF_L   LONG_MAX
#define NINF_L   LONG_MIN
#define INF_U   UINT_MAX
#define INF     INT_MAX
#define NINF     INT_MIN

#define inf INF_LL

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;

#define NMAX 50001

int n,m, N;
vector<ll> H;
vector<ll> A;
vector<ll> P;
vector<vector<ii> > G;

void hswap(int i, int j){
  int old_order_i = H[i];
  int old_order_j = H[j];
  int tmp = H[i];
  H[i] = H[j];
  H[j] = tmp;
  P[old_order_i] = j;
  P[old_order_j] = i;
}

void percolate(int n, int i){
  while(i >= 1){
    if(A[H[i]] < A[H[i/2]]){
      hswap(i, i/2);
      i /= 2;
    }
    else
      break;
  }
}

void sift(int n, int i){

  while(i <= n){
    if(2*i+1 <= n){
      if(A[H[i]] < A[H[2*i]] && A[H[i]] < A[H[2*i+1]])
        break;
      if(A[H[2*i]] < A[H[2*i+1]]){
        hswap(i, 2*i);
        i = 2*i;
      }
      else{
        hswap(i, 2*i+1);
        i = 2*i+1;
      }
    }
    else if(2*i <= n){
      if(A[H[i]] < A[H[2*i]])
        break;
      hswap(i, 2*i);
      i = 2*i;
    }
    else  // we are at a leaf.
      break;
  }
}

void build_heap(int n){
  for(int i=n/2; i>=1; --i){
    sift(n, i);
  }
}

void extract(int &n, int i){
  int pos = i;
  P[H[i]] = -1;
  H[pos] = H[n];
  n--;
  if((2*pos <= n && A[H[pos]] > A[H[2*pos]]) || (2*pos+1 <= n && (A[H[pos]] > A[H[2*pos]] || A[H[pos]] > A[H[2*pos+1]])))
    sift(n, pos);
}


void dijkstra(){
    while(n){
      int v = H[1];
      //cout << "v: " << v << endl;
      extract(n, 1);
      /*
      cout << "after extract:\n";
      for(int i=1; i<=n; ++i)
        cout << "graph node: " << H[i] << " dist: " << A[H[i]] << "\n";
      cout << "\n";
      */
      for(int i=1; i<G[v].size(); ++i){
        int u = G[v][i].first;
        ll c = G[v][i].second;
        if(P[u] != -1){
          if(A[v] + c < A[u]){
            A[u] = A[v] + c;
            int pos = P[u];
            if(pos != 1){
              //cout << u << " needs to be rescheduled\n";
              if(A[H[pos]] < A[H[pos/2]])
                percolate(n,pos);
              else if((2*pos <= n && A[H[pos]] > A[H[2*pos]]) || (2*pos+1 <= n && (A[H[pos]] > A[H[2*pos]] || A[H[pos]] > A[H[2*pos+1]])))
                sift(n, pos);
              }
            }
        }
      }

      /*
      for(int i=1; i<=n; ++i)
        cout << "graph node: " << H[i] << " dist: " << A[H[i]] << "\n";
      cout << "\n";
      */
    }
}



int main(){

  freopen("dijkstra.in", "r", stdin);
  //freopen("grader_test2.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  scanf("%d %d", &n, &m);
  G.resize(n, vector<ii>());
  for(int i=0; i<m; ++i){
    int from, to, cost;
    scanf("%d %d %d", &from, &to, &cost);
    from--;
    to--;
    G[from].push_back(make_pair(to, cost));
  }

  vector<ll> dist(n, inf);
  dist[0] = 0;
  priority_queue<ii, vector<ii>, greater<ii> > pq;
  pq.push(ii(0,0));

  while(!pq.empty()){
    ii top = pq.top(); pq.pop();
    int d = top.first, u = top.second;
    //cout << u << endl;
    if(d == dist[u]){
      for(int i=0; i<G[u].size(); ++i){
        int v = G[u][i].first;
        int weight_u_v = G[u][i].second;
        //cout << "v: " << v << endl;
        if(dist[u] + weight_u_v < dist[v]){
          dist[v] = dist[u] + weight_u_v;
          pq.push(ii(dist[v], v));
        }
      }
    }
  }

  for(int i=1; i<n; ++i)
    if(dist[i] >= inf)
      cout << 0 << " ";
    else
      cout << dist[i] << " ";
    cout << "\n";
  /*
  scanf("%d %d", &n, &m);
  N = n;
  G.resize(n+1, vector<pair<ll, ll> >(1,make_pair(0,inf)));
  for(int i=0; i<m; ++i){
    int from, to, cost;
    scanf("%d %d %d", &from, &to, &cost);
    G[from].push_back(make_pair(to, cost));
  }

  A.resize(n+1, inf);
  int s = 1;
  A[s] = 0;
  for(int i=1; i<G[s].size(); ++i)
    A[G[s][i].first] = G[s][i].second;

  P.resize(n+1, 0);
  H.resize(n+1,0);
  for(int i=1; i<=n; ++i)
    H[i] = P[i] = i;
  build_heap(n);

  dijkstra();
  //cout << "dist: ";
  for(int i=2; i<=N; ++i)
    if(A[i] >= inf)
      cout << 0 << " ";
    else
      cout << A[i] << " ";
  cout << "\n";
  */

  return 0;
}