#include <iostream>
#include<fstream>
#define INF 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]=INF;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        f>>cost[x][y];
    }
    viz[1]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=cost[1][i];
    }
    int min;
    do
    {
        min=INF;
        for(i=1;i<=n;i++)
            if(d[i]<min && viz[i]==0)
            {
                min=d[i];
                vf=i;
            }
    if(min<INF)
    {
        viz[vf]=1;
        for(i=1;i<=n;i++)
        if(d[vf]+cost[vf][i]<d[i]&&viz[i]==0)
        {
            d[i]=d[vf]+cost[vf][i];

        }
    }
    }while(min<INF);
  /*  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[N]={0};
    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]==INF)
            g<<0<<" ";
        else
            g<<d[i]<<" ";


}