#include <iostream>
#include <fstream>
#include <limits.h>

using namespace std;

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

int n,m,costuri[100][100],drumuri[100],viz[100];

void citire_graf()
{
    f>>n>>m;
    int x,y,val;
    for(int i=1;i<=n;++i)
        drumuri[i]=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i!=j)
                costuri[i][j]=INT_MAX;
        }
    }
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>val;
        if(x==1)
            drumuri[y]=val;
        costuri[x][y]=val;
    }
}

void dijkstra()
{
    viz[1]=1;
    for(int i=2;i<=n;++i)
    {
        int minim=INT_MAX;
        int nodx;
        for(int j=2;j<=n;++j)
        {
            if(viz[j]==0&&drumuri[j]<minim&&drumuri[j]!=0)
            {
                minim=drumuri[j];
                nodx=j;
            }
        }
        viz[nodx]=1;
        for(int j=2;j<=n;j++)
        {
            if(drumuri[j]>drumuri[nodx]+costuri[nodx][j] && costuri[nodx][j]!=INT_MAX)
            {
                drumuri[j]=drumuri[nodx]+costuri[nodx][j];
            }
        }
    }
}

int main()
{
    citire_graf();
    dijkstra();
    for(int i=2;i<=n;++i)
        g<<drumuri[i]<<' ';
    return 0;
}