#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
unsigned int n,m, s[inf], d[inf];
vector <int> a[inf], v[inf];
void citire()
{
    int i,j,k,c;
    f>>n>>m;

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

void dijkstra(int start)
{
    int i,mn,poz,k;
    for(i=0; i<v[start].size(); i++)
    {
        d[v[start][i]]=a[start][i];
    }
    for(i=1; i<=n; i++)
        if(i!=start && d[i]==0)
        d[i]=inf;
    d[start]=0;
    s[start]=1;
    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=0; i<a[poz].size(); i++)
            if(s[v[poz][i]]==0)
            if(d[v[poz][i]]>mn+a[poz][i])
        {
            d[v[poz][i]]=mn+a[poz][i];
        }
    }

}

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