#include <iostream>
#include <fstream>
using namespace std;

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

#define INF 999999

int n,m,cost[1000][1000],t[1000],s[1000],d[1000];

void Citire()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                cost[i][j]=INF;
    for(int c,i,j,k=1;k<=m;k++)
    {
        fin>>i>>j>>c;
        cost[i][j]=c;
    }

}

void Dijkstra(int r)
{
    int Min;
    for(int i=1;i<=n;i++) d[i]=cost[r][i];
    for(int i=1;i<=n;i++) t[i]=r,s[i]=0;
    s[r]=1,t[r]=0;
    for(int i=1;i<n;i++)
    {
        Min=INF;
        for(int j=1;j<=n;j++)
            if(s[j]==0&&d[j]<Min)
                i=j,Min=d[j];
        s[i]=1;
        for(int j=1;j<=n;j++)
            if(d[j]>d[i]+cost[i][j])
                d[j]=d[i]+cost[i][j],t[j]=i;
    }
}

int main()
{
    Citire();
    Dijkstra(1);
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";

    return 0;
}