#include <iostream>
#include <fstream>
#include <vector>
#define nmax 50005
#define Inf 1000000000
using namespace std;

int n,m,startNode;
vector<int> d,t,s;
vector< vector<int> > A;

void initializare()
{
    int x,y,i,c;
    cin>>n>>m;
    t.assign(n+2,0);
    for(int i=0;i<=n;i++)
    {
        A.push_back(t);
        A[i].assign(n+2,Inf);
    }

    while(cin>>x>>y>>c)
        A[x][y]=c;

    d.push_back(0);

    for(i=1; i<=n; i++)//Distantele initiale de la nodul 1 la celelalte noduri din graf
    {
        d[i]=A[startNode][i];
        d.push_back(A[startNode][i]);
        if(A[startNode][i]<Inf)
            t[i]=startNode;
    }

}


void drum(int y)//afisare drum
{
    if(t[y]!=0)
    {
        drum(t[y]);
        cout<<t[y]<<' ';
    }
}

void Dijkstra()
{
    int nrDistanteRezolvate,dmin,im,i;
    s.assign(n+2,0);
    s[startNode]=1;
    nrDistanteRezolvate=1;
    do
    {
        dmin=Inf;
        for(i=1; i<=n; i++)
            if(!s[i] && d[i]<dmin)
            {
                im=i;
                dmin=d[i];
            }
        if(dmin<Inf)
        {
            nrDistanteRezolvate++;
            s[im]=1;
            for(i=1; i<=n; i++)
                if(!s[i] && d[i]>d[im]+A[im][i])
                {
                    d[i]=d[im]+A[im][i];
                    t[i]=im;
                }
        }
    }
    while(!(dmin==Inf || nrDistanteRezolvate==n));

    for(i=2; i<=n; i++)
        if(d[i]==Inf)
            cout<<0<<' ';
        else
            cout<<d[i]<<' ';
    cout<<'\n';
}

int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);

    startNode=1;
    initializare();
    Dijkstra();
}