#include <iostream>
#include <fstream>

using namespace std;
const int inf=9999999;
//algoritmul lui Dijkstra-calculeaza distanta minima de la 1 nod la toate celelalte
int main()
{   int m,n,i,j,x,y,d,a[100][100]={0},t[100],v[100],q[100];
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)
        q[i]=inf;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i!=j)
            a[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>d;
        a[x][y]=d;

    }
    t[1]=0;
    v[1]=1;
    q[1]=0;
    for(i=2;i<=n;i++)
        if(q[i]>a[1][i])
    {
        q[i]=a[1][i];
        t[i]=1;
    }
    int ok=1;
    while(ok)
    {
        int Min=inf;
        int poz=0;
        for(i=2;i<=n;i++)
            if(q[i]<Min&&v[i]==0)
                {Min=q[i];
                poz=i;}

        if(poz==0)
            ok=0;
        else
        {v[poz]=1;
            for(i=1;i<=n;i++)
            {
                int dnou=q[poz]+a[poz][i];

                if(v[i]==0 && q[i]>dnou)
            {
                q[i]=dnou;
                t[i]=poz;
            }
            }
        }


    }
    for(i=2;i<=n;i++)
        g<<q[i]<<" ";
    return 0;
}