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

using namespace std;

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

const int NMAX = 5e4+5;

struct muchie{
  int nod,cost;
  bool operator < (const muchie x) const{
      return x.cost<cost;
  }
};
int n,m,s,d[NMAX];
vector<muchie>g[NMAX];
priority_queue<muchie>Q;
void read(){
  fin>>n>>m;
  for(int i=1;i<=m;++i){
     int x,y,c;
     fin>>x>>y>>c;
     g[x].pb({y,c});
  }
}
void dijkstra(int nod){
  for(int i=1;i<=n;++i)
    d[i]=INF;
  Q.push({nod,0});
  d[nod]=0;
  while(!Q.empty()){
     int nod=Q.top().nod;
     int cost=Q.top().cost;
     Q.pop();
     for(auto x:g[nod]){
        if(cost+x.cost<d[x.nod]){
            d[x.nod]=cost+x.cost;
            Q.push({x.nod,cost+x.cost});
        }
     }
  }
}
void solve(){
  dijkstra(1);
  for(int i=1;i<=n;++i)
    if(d[i]!=INF && d[i]!=0)
      fout<<d[i]<<" ";
}
int main(){
 read();
 solve();
 return 0;
}