#include <iostream>
#include <fstream>
#define INF 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a[102][102],v[102],d[102],t[102],n,x,i,c1,c2,c3,m;
void citire()
{
    int i,j,c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i==j)a[i][j]=0;
            else a[i][j]=INF;
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>c1>>c2>>c3;
        a[c1][c2]=c3;
    }
}
void dijkstra(int x)
{
    int i,j,mi,ok=1,k;
    for(i=1;i<=n;i++)
    {
        d[i]=a[x][i];
        if((d[i]<INF)and(d[i]>0))t[i]=x;
    }
    v[x]=0;
    t[x]=0;
    while(ok)
    {
        mi=INF;
        for(i=1;i<=n;i++)// cautam cel mai apropiat nod de x
        {
            if((v[i]==0)and(mi>d[i]))
            {
                mi=d[i];
                k=i;
            }
        }
        if(mi==INF)ok=0;
        else
        {
            v[k]=1;//marcam nodul ca fiind vizitat
            //parcurgem nodurile adiacente si actualizam vectorul d si t
            for(i=1;i<=n;i++)
            {
                if((v[i]==0)and(d[i]>d[k]+a[k][i]))
                {
                    d[i]=d[k]+a[k][i];
                    t[i]=k;
                }
            }
        }
    }
}
int main()
{
    citire();
    dijkstra(1);
    for(i=1;i<=n;i++)
    {
        if(d[i]!=0)fout<<d[i]<<" ";
    }
}