#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define ll long long
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
ll n,m,i,j,k,d[50001],c[50001];vector<pair<ll,ll>>a[50001];map<ll,bool>b;
int main()
{
fill(d,d+50001,0);fill(c,c+50001,INT_MAX);
in>>n>>m;
while(m--)
    in>>i>>j>>k,a[i].push_back(make_pair(j,k));
b[1]=1,c[1]=1;
while(b.empty()==0)
{
    k=b.begin()->first;
    b.erase(b.begin());
    //cout<<(k&USHRT_MAX)<<' '<<(k>>16)<<'\n';
    d[k&USHRT_MAX]=k>>16;
    k&=USHRT_MAX;
    for(auto i=a[k].begin();i!=a[k].end();++i)
        if((((i->second+d[k])*1ll)<<16)+i->first<c[i->first])
            b.erase(c[i->first]),c[i->first]=(((i->second+d[k])*1ll)<<16)+i->first,b[c[i->first]]=1;
}
for(i=2;i<=n;i++)out<<d[i]<<' ';
}