#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define SIZE 50005
#define INF 184467440737095516
using namespace std;
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");
class Dijkstra
{
    long long n;//nr de noduri
    long long m;//nr de muchii
    long long d[SIZE];//distantele de la nodul star la nodul i+1
    vector<vector< pair<long long,long long> > > A;

public:
    Dijkstra();
    void dijkstra(long long x);
    void citire();
    void afisare();


};

Dijkstra::Dijkstra()
{
    n=0;
    m=0;
}

void Dijkstra::citire()
{
    long long x,y,z;

    f>>n>>m;
    A.resize(n+1);
    for(long long i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        A[x].push_back(make_pair(-z,y));
    }

}

void Dijkstra::afisare()
{
    for(long long i=2;i<=n;i++)
        if(d[i]==INF)
            g<<0<<" ";
        else
            g<<d[i]<<" ";
}


void Dijkstra::dijkstra(long long x)
{
    long long nr=0;
    for(long long i=2;i<=n;i++)
        d[i]=INF;


    d[1]=0;
    long long k=1;
    while(k<n)
    {

        int ct=0;
        make_heap(A[k].begin(),A[k].end());

        while(ct<A[k].size())
        {
            if(d[A[k][ct].second]>d[k]-A[k][ct].first)
                d[A[k][ct].second]=d[k]-A[k][ct].first;
                ct++;
                nr++;
        }

        k++;

    }


}

int main()
{
    Dijkstra D;
    D.citire();
    D.dijkstra(1);
    D.afisare();
    return 0;
}