#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct muchie
{
    int nod,Cost=10000000;


};
bool operator <(muchie a,muchie b)
{
    if(a.Cost<b.Cost)
        return false;
    return true;
}
int n,m;
int a,b,c;
int distMin[50003];
vector <muchie> vecini[50003];
priority_queue<muchie> coada;
int main()
{
    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fi>>a>>b>>c;
        muchie noua;
        noua.nod=b;
        noua.Cost=c;
        vecini[a].push_back(noua);

    }

    for(int i=1; i<=n; i++)
        distMin[i]=100000000;


    muchie start;
    start.Cost=0;
    start.nod=1;
    distMin[1]=0;
    coada.push(start);


    while(coada.empty()==false)
    {
        int CostCurent=coada.top().Cost;
        int Curent=coada.top().nod;
        coada.pop();

        if(CostCurent!=distMin[Curent])
            continue;

        for(muchie v:vecini[Curent])
        {
            if(  distMin[v.nod]>distMin[Curent]+v.Cost )
            {
                distMin[v.nod]=distMin[Curent]+v.Cost;
                muchie adaug;
                adaug=v;
                adaug.Cost=distMin[adaug.nod];
                coada.push(adaug);
            }
        }
    }


    for(int i=2; i<=n; i++)
        if(distMin[i]==100000000)
            fo<<0<<" ";
        else
            fo<<distMin[i]<<" ";


    fi.close();
    fo.close();
    return 0;
}