#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 50001
#define INF 1000000000
using namespace std;
int n,x0;
int dmin[Nmax];
vector<pair<int,int> >G[Nmax];
vector<pair<int,int> >::iterator it;
queue <int> C;
void citire()
{
    int i,m,x,y,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
    }
}
void dijkstra()
{
    int i,x;
    for(i=1;i<=n;++i) dmin[i]=INF;
    dmin[1]=0;
    C.push(1);
    while(!C.empty())
    {
        x=C.front();C.pop();
        for(it=G[x].begin();it!=G[x].end();++it)
         if (dmin[it->first]>dmin[x]+it->second)
         {
             dmin[it->first]=dmin[x]+it->second;
             C.push(it->first);
         }
    }
}
void afisare()
{
    int j;
        for(j=2;j<=n;++j)
        if (dmin[j]!=INF) printf("%d ",dmin[j]);
        else printf("%d ",0);
}
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}