using namespace std;
#define MAX 50005
#define pb push_back
#include<cstdio>
#include<fstream>
#include<vector>
#define INFINIT 2000000000
struct nod{
    int capat,c;
    nod *next;
};

nod *G[MAX];
int v[MAX], d[MAX],apar[MAX],n;

void addarc(int x,int y,int c)
{
    nod *p=new nod;
    p->capat=y;
    p->c=c;
    p->next=G[x];
    G[x]=p;
}

int bmf(int sursa)
{
    vector<int> coada;
    int st,dr;
    coada.pb(sursa);
    st=dr=0;
    v[sursa]=1;
    d[sursa]=0;
    while(st<=dr)
    {
        int k=coada[st];
        v[k]=0;
        st++;
        if(d[k]<INFINIT)
        for(nod *p=G[k] ; p ; p=p->next)
        {
            int vecin=p->capat;
            if(d[vecin]>d[k]+p->c)
            {
                d[vecin]=d[k]+p->c;
                if(v[vecin]==0)
                {
                    if(apar[vecin]>n)
                        return 1;
                    v[vecin]=1;
                    apar[vecin]++;
                    coada.pb(vecin);
                    dr++;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int m,i;
    ifstream fin("dijkstra.in");
    freopen("dijkstra.out","w",stdout);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        addarc(x,y,c);
    }
    for(i=1;i<=n;i++)
        d[i]=INFINIT,v[i]=0;
    bmf(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==INFINIT)
            printf("0 ");
        else
            printf("%d ", d[i]);
    }
    return 0;
}