#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];
priority_queue < pair<int,int> > q;

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=1; i<=n; i++)
        if(i!=start && d[i]==0)
            d[i]=inf;

    q.push({0, start });
    while(!q.empty())
    {
        poz=q.top().second;
        q.pop();
        s[poz]=1;
        for(i=0; i<a[poz].size(); i++)
            if(s[v[poz][i]]==0)
            if(d[v[poz][i]]>d[poz]+a[poz][i])
        {
            d[v[poz][i]]=d[poz]+a[poz][i];
            q.push({ -d[v[poz][i]], v[poz][i] });
        }
    }
}

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