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

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int oo=20000;
const int NMax=500;
const int MMax=250005;

int matrice[NMax][NMax], n, m;

void citire()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j)
                matrice[i][j]=oo;
    int a, b, c;
    while(f>>a>>b>>c)
        matrice[a][b]=c;
}

int distanta[NMax];
bool vizitat[NMax];

void dijkstra()
{
    vizitat[1]=true;

    for(int j=1; j<=n; j++)
        distanta[j]=matrice[1][j];

    int distanta_minima, varf;

    for(int i=1; i<=n; i++)
    {
        distanta_minima=oo;

        for(int j=2; j<=n; j++)
            if(vizitat[j]==false)
                if(distanta[j]<distanta_minima)
                {
                    distanta_minima=distanta[j];
                    varf=j;
                }

        vizitat[varf]=true;

        for(int j=1; j<=n; j++)
            if(vizitat[j]==false)
                if(distanta[varf]+matrice[varf][j]<distanta[j])
                    distanta[j]=distanta[varf]+matrice[varf][j];
    }

    for(int i=2; i<=n; i++)
        g<<distanta[i]<<" ";
}

int main()
{
    citire();
    dijkstra();
    return 0;
}