#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define INFINIT 100000000
int a[101][101],viz[101],t[101],d[101];
int n,r,i,j,minim,poz,k1,k2,k3,m;

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=INFINIT;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f>>k1>>k2>>k3;
            a[k1][k2]=k3;
        }
        r=1;
    viz[r]=1;

    for(i=1;i<=n;i++)
    {
        d[i]=a[r][i];
        if(d[i]<INFINIT && r!=i)
            t[i]=r;
    }

    for(i=1;i<n;i++)
    {
        minim=INFINIT;
        for(j=1;j<=n;j++)
        {
            if(viz[j]==0)
            {
                if(d[j]<minim)
                {
                    minim=d[j];
                    poz=j;
                }
            }
        }
        for(j=1;j<=n;j++)
        {
            if(viz[j]==0)
            {
                if(d[j]>d[poz]+a[poz][j])
                {
                    d[j]=d[poz]+a[poz][j];
                    t[j]=poz;
                }
            }
            viz[poz]=1;
        }
    }
    /*for(i=1;i<=n;i++)
    {
        if(i!=r)
        {
            g<<d[i]<<" ";
            j=i;
            while(j!=0)
            {
                g<<j<<" ";
                j=t[j];
            }
            g<<'\n';
        }
    } */
    for(i=2;i<=n;i++)
    {
        if(i==r)
            g<<0;
        else
        {
            if(d[i]==INFINIT)
                g<<0;
            else g<< d[i];
        }
        g<<" ";
    }

    return 0;
}