#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define INF 10000000
fstream f(IN, ios::in), g(OUT, ios::out);
int n, m, s, a[1000][1000], done[10000], cost[10000], prov[10000], cos, i, j, x, y;
int visit_all(int start)
{
    int minim=INF, care=0, i;
    for(i=1; i<=n; i++)
    {
        if(a[start][i]!=INF && a[start][i]!=0 && i!=start)
        {
            if(cost[i]>cost[start]+a[start][i])
            {
                cost[i]=cost[start]+a[start][i];
                prov[i]=start;
            }
        }
        if(cost[i]<minim && done[i]==0)
        {
            minim=cost[i];
            care=i;
        }
    }
    done[care]=1;
    return care;
}
void DIJ(int S)
{
    int X, i;
    X=S;
    done[X]=1;
    cost[X]=0;
    prov[X]=1;
    for(i=1; i<=n; i++)
        X=visit_all(X);
}
int main()
{
    f>>n>>m;
    s=1;
    for(i=1; i<=n; i++)
    {
        cost[i]=INF;
        done[i]=0;
        prov[i]=0;
    }
    for(i=1; i<=n; i++)
    {
        cout<<cost[i]<<" ";
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            a[i][j]=INF;
            if(i==j)
                a[i][j]=0;
        }
    }
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>cos;
        a[x][y]=cos;
    }
    DIJ(s);
    for(i=2; i<=n; i++)
    {
        if(cost[i]==INF)
            g<<"0 ";
        else
            g<<cost[i]<<" ";
    }
}