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

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

struct nod
{
    int cost=0;
    int actualNod=0;
};
bool operator <(nod a,nod b)
{
    if(a.cost<b.cost)
        return false;

    return true;
}
int n,m;
priority_queue<nod> coada;
vector <nod> vecini[50004];
int distMin[50004];

int main()
{

    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        fi>>a>>b>>c;

        nod nou;
        nou.actualNod=b;
        nou.cost=c;
        vecini[a].push_back(nou);
    }


    fill(distMin+1,distMin+n+1,100000000);
    nod start;
    start.actualNod=1;
    start.cost=0;
    distMin[1]=0;
    coada.push(start);



    while(coada.empty()==false && coada.top().actualNod!=n)
    {
        nod curent=coada.top();
        coada.pop();

        for(nod vec:vecini[curent.actualNod])
        {
            if(distMin[vec.actualNod]>curent.cost+vec.cost)
            {
                nod v;
                v=vec;
                v.cost+=vec.cost;
                coada.push(v);
                distMin[vec.actualNod]=distMin[curent.actualNod]+vec.cost;
            }
        }
    }


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

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