#include <iostream>
#include <fstream>
#include <vector>
#define inf 100000

using namespace std;

ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");

int d[50050], nod1[50050],nod2[50050],cost[50050];
int n,m;

int main()
{
    int i, ok=1;
    in>>n>>m;

    for(i=2; i<=n; i++)
        d[i]=inf;

    for(i=0; i<m; i++)
    {
        in>>nod1[i]>>nod2[i]>>cost[i];
        if(nod1[i]==1)
            d[nod2[i]]=cost[i];
    }

    while(ok)
    {
        ok=0;
        for(i=0; i<m; i++)
            if(d[nod2[i]]>d[nod1[i]]+cost[i])
            {
                d[nod2[i]]=d[nod1[i]]+cost[i];
                ok=1;
            }
    }

    for(i=2; i<=n; i++)
        if(d[i]==inf)
            out<<0<<' ';
        else
            out<<d[i]<<' ';


    return 0;
}