#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
short n,m,poz,i,j,c;
long ma,mi,d[22269];
bool s[22269];
int a[22269][22269];
int main()
{
    ma=495863825;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=ma;
            else
                a[i][j]=0;
    while(fin>>i>>j>>c)
        a[i][j]=c;
    s[1]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=a[1][i];
    }
    for(i=1;i<n;i++)
    {
        mi=ma;
        for(j=1;j<=n;j++)
            if(!s[j])
            if(d[j]<mi)
        {
            mi=d[j];
            poz=j;
        }
        s[poz]=1;
        for(j=1;j<=n;j++)
        if(d[j]>d[poz]+a[poz][j]&&s[j]==0)
        {
            d[j]=d[poz]+a[poz][j];
        }
    }
     for(i=2;i<=n;i++)
        if(d[i]<ma)
        fout<<d[i]<<" ";
     else
        fout<<"0 ";



}