#include <iostream>
#include<fstream>
#define OO 150000
#define N 10001
using namespace std;
int cost[N][N], d[N];
int main()
{
    fstream f("dijkstra.in",ios::in),g("dijkstra.out",ios::out);
    int i,j,m,n,vf,x,y,viz[N]={0};
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                cost[i][j]=OO;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        f>>cost[x][y];
    }

    for(i=1;i<=n;i++)
        d[i]=cost[1][i];
    int min;
    viz[1]=1;
   do
    {
        min=OO;
        for(i=1;i<=n;i++)
            if(min>d[i]&&viz[i]==0)
            {
                min=d[i];
                vf=i;
            }
        if(min<OO)
        {
            viz[vf]=1;
            for(i=1;i<=n;i++)
                if(d[i]>d[vf]+cost[vf][i]&&viz[i]==0)
                    d[i]=d[vf]+cost[vf][i];
        }
    }
    while(min!=OO);
    for(i=2;i<=n;i++)
        if(d[i]==OO)
            g<<0<<" ";
        else
            g<<d[i]<<" ";


}