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

class Dijkstral
{
    int n;//nr de noduri
    int m;//nr de muchii
    int d[50000];//distantele de la nodul star la nodul i+1
    vector<pair<int,int> > A[100];
public:
    Dijkstral();
    void dijkstral(int x);
    void citire(ifstream &f);
    void afisare(ofstream&g);


};

Dijkstral::Dijkstral()
{
    cout<<"Apelare constructor\n";
    n=0;
    m=0;
}

void Dijkstral::citire(ifstream &f)
{
    int x,y,z;

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

}

void Dijkstral::afisare(ofstream&g)
{
    for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
}

void Dijkstral::dijkstral(int x)
{
    for(int i=2;i<=n;i++)
        d[i]=100000000;


    d[1]=0;
    int 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++;
        }

        k++;

    }
}

int main()
{
    Dijkstral D;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    D.citire(f);
    D.dijkstral(1);
    D.afisare(g);
    return 0;
}