#include <iostream>
#include<fstream>
#include<algorithm>
#define N 5005
#define inf 2000000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");



int n,m,concert,p;

int a[N][N];
int d[N];//dist min de la concert la celelalte noduri
bool f[N];//selectat

void read()
{
    int i,j,x,y,c;
    fin>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
    }


}

int dijkstra()
{

    int i,j,dmin,next;

    for(i=1;i<=n;++i)
        d[i]=a[1][i];
    f[1]=1;d[1]=0;

    for(i=1;i<=n-1;++i)
    {
        dmin=inf;
        for(j=1;j<=n;++j)
            if(d[j]<dmin&&f[j]==0)
        {
            dmin=d[j];
            next=j;
        }
        f[next]=1;
        for(j=1;j<=n;++j)
            if(f[j]==0&&d[j]>d[next]+a[next][j])
                d[j]=d[next]+a[next][j];

    }

    for(i=2;i<=n;++i)
    if(d[i]==inf)
        fout<<0<<" ";
    else fout<<d[i]<<" ";

}


void initializare()
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        a[i][j]=inf;
}

int main()
{
    fin>>n;
    initializare();
    read();
    dijkstra();



    return 0;
}