#include <bits/stdc++.h>
#define Nmax 50001
#define INF 2e9+5
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graph
{
    vector < pair<int,int> > v;
};
graph G[Nmax];
int cost[Nmax];
int vct[Nmax];
inline bool cmp(const int &x, const int &y)
{
    return cost[x]>cost[y];
}
int main()
{int n,m,i,j,k,x;
f>>n>>m;
for(k=1;k<=m;k++)
{
    f>>i>>j>>x;
    G[i].v.push_back({j,x});
}
fill(cost+2,cost+n+1,INF);
for(i=1;i<=n;i++)
vct[i]=i;
make_heap(vct+1,vct+n+1,cmp);
m=n;
for(j=1;j<n;j++)
{
    x=vct[1];
    pop_heap(vct+1,vct+m+1,cmp);
    m--;
    for(i=0;i<G[x].v.size();i++)
    if(cost[G[x].v[i].first]>cost[x]+G[x].v[i].second)
        cost[G[x].v[i].first]=cost[x]+G[x].v[i].second;
}
for(i=2;i<=n;i++)
if(cost[i]==INF) g<<0<<' ';
else g<<cost[i]<<' ';

    return 0;
}