#include<fstream>
#include<queue>
#include<vector>
#define inf 0x3f3f3f 
#define pii pair<int,int> 
#define dim 50002
using namespace std;ifstream cin("dijkstra.in");ofstream cout("dijkstra.out");int n,m;int d[dim],v[dim];vector<pii>V[dim];struct comp{bool operator()(int a,int b){return d[a]>d[b];}};priority_queue<int,vector<int>,comp>Q;void djk(){for(int i=2;i<=n;++i)d[i]=inf;v[1]=1;Q.push(1);while(!Q.empty()){int nd=Q.top();v[nd]=0;Q.pop();for(auto vec:V[nd]){int cst=vec.second;int nbr=vec.first;if(d[nbr]>d[nd]+cst){d[nbr]=d[nd]+cst;if(!v[nbr]){Q.push(nbr);v[nbr]=1;}}}}}
int main()
{cin>>n>>m;for(;m;--m){int a,b,c;cin>>a>>b>>c;V[a].push_back({b,c});}
djk();for(int i=2;i<=n;++i)cout<<d[i]<<" ";return 0;}