#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("d.in");
ofstream g("d.out");
int n,a[101][101];

int d[101],viz[101],t[101];


int nmin()
{int mini=10000,p=0;
    for(int i=1;i<=n;i++)
    if(d[i])
        if(viz[i]==0)
        if(mini>d[i])
        p=i,mini=d[i];
    return p;

}

int main()
{int x,y,c1,i,j,p=1,n1,k,m;
    f>>n>>m;
    while(f>>x)
    {
        f>>y>>c1;
        a[x][y]=c1;

    }

    viz[p]=1;
    for(i=1;i<=n;i++)
        if(a[p][i])
            d[i]=a[p][i],t[i]=p;
    k=nmin();
    while(k)
    {


        viz[k]=1;
        for(i=1;i<=n;i++)
            if(!viz[i])
            if(d[k]*a[k][i])
            if(d[i]==0 or d[i]>d[k]+a[k][i])
            d[i]=d[k]+a[k][i],t[i]=k;
            k=nmin();
    }

    /*for(i=1;i<=n;i++)
        if(d[i]==0)
        d[i]=-1;
    d[p]=0;*/

    for(i=2;i<=n;i++)
        g<<d[i]<<' ';

    return 0;
}