#include <bits/stdc++.h>
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX = 5e5+5;

int n,m,d[NMAX];
bitset<NMAX>vis;
vector<pair<int,int> >g[NMAX];
priority_queue<pair<int,int> >Q;
void read(){
  fin>>n>>m;
  for(int i=1;i<=m;++i){
    int x,y,c;
    fin>>x>>y>>c;
    g[x].pb({c,y});
  }
}
void dijkstra(int x){
  for(int i=1;i<=n;++i)
    d[i]=INF;
  d[x]=0;
  Q.push({0,x});
  while(!Q.empty()){
    int nod=Q.top().second;
    Q.pop();
    if(vis[n]==0){
        vis[nod]=1;
        for(auto x:g[nod]){
            if(x.first+d[nod]<d[x.second]){
                d[x.second]=x.first+d[nod];
                Q.push({-d[x.second],x.second});
            }
        }
    }
  }
}
void solve(){
  dijkstra(1);
  for(int i=2;i<=n;++i)
     if(d[i]!=INF)
       fout<<d[i]<<" ";
}
int main(){
 read();
 solve();
 return 0;
}