#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 5001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m, s[inf], t[inf], d[inf], a[inf][inf];

void citire()
{
    int i,j,k,c;
    f>>n>>m;

    for(i=1; i<=n; i++)
    for(j=1; j<=n; j++)
        if(i!=j)
            a[i][j]=inf;

    for(k=1; k<=m; k++)
    {
       f>>i>>j>>c;
       a[i][j]=c;
    }
}

void dijkstra(int start)
{
    int i,mn,poz,k;
    for(i=1; i<=n; i++)
    if(i!=start)
    {
        d[i]=a[start][i];
        s[i]=0;
        if(d[i]<inf)
            t[i]=start;
    }
    d[start]=0;
    s[start]=1;
    t[start]=0;
    for(k=1; k<n; k++)
    {mn=inf;
        for(i=1; i<=n; i++)
            if(s[i]==0 && d[i]<mn)
        {
            mn=d[i];
            poz=i;
        }
        s[poz]=1;
        for(i=1; i<=n; i++)
            if(s[i]==0)
            if(d[i]>d[poz]+a[poz][i])
        {
            d[i]=d[poz]+a[poz][i];
            t[i]=poz;
        }
    }

}

int main()
{
    citire();
    dijkstra(1);
    for(int i=2; i<=n; i++)
        g<<d[i]<<" ";
    f.close();
    g.close();
    return 0;
}