#include<cstdio>
#include<vector>
#include<utility>
#define oo 500000000
using namespace std;
vector <pair<int,int> > v[50010];
int n,m,viz[50010],cost[50010],coada[50010];
void citire()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            v[a].push_back(make_pair(b,c));
        }
}
void initializare()
{
    for(int i=1;i<=n;i++)
        cost[i]=oo;
}
void bellman_ford(int x0)
{
    int prim=1,ultim=1,k;
    coada[ultim]=x0;
    viz[x0]=1;
    cost[x0]=0;
    while(prim<=ultim)
    {
        k=coada[prim];
        viz[k]=0;
        prim++;
        for(vector <pair<int, int> >::iterator it=v[k].begin();it!=v[k].end();++it)
            if(cost[(*it).first]>cost[k]+(*it).second)
                {
                    cost[(*it).first]=cost[k]+(*it).second;
                    if(viz[(*it).first]==0)
                        {
                            coada[++ultim]=(*it).first;
                            viz[(*it).first]=1;
                        }
                }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(cost[i]!=oo) printf("%d ",cost[i]);
        else printf("0 ");
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    initializare();
    bellman_ford(1);
    afisare();
    return 0;
}