#include <vector>

#include <fstream>

#include <utility>

#include <functional>

#include <set>
using namespace std;
class graf
{
    int n;
    int m;
    vector<vector<pair<int,int>>>gr;

public:
    graf()
    {
        ifstream citire("dijkstra.in");
        citire>>n;
        citire>>m;
        gr.resize(n+1);

        for(int i=0;i<m;i++)
        {
            pair<int,int>temp;
             int j;

            citire>>j>>temp.first>>temp.second;
            gr[j].push_back(temp);
        }
        citire.close();
    }

    void dijkstra()
    {
        vector<int>distanta(n+1,999);
        distanta[1]=0;
        vector<int>parinte(n+1,0);
        set<pair<int,int>>q;
        q.insert(make_pair(0,1));
        while(!q.empty())
        {
            int nod_curent=q.begin()->second;

            q.erase(q.begin());
            for(int i=0;i<gr[nod_curent].size();i++)
            {
                int distanta_noua=distanta[nod_curent]+gr[nod_curent][i].second;
                if(distanta_noua<distanta[gr[nod_curent][i].first])
                {
                    parinte[gr[nod_curent][i].first]=nod_curent;
                    pair<int,int>cautare=make_pair(distanta[gr[nod_curent][i].first],gr[nod_curent][i].first);
                    if(q.count(cautare))
                        q.erase(cautare);

                    distanta[gr[nod_curent][i].first]=distanta_noua;
                    //cautare=make_pair(distanta[gr[nod_curent][i].first],gr[nod_curent][i].first);
                    q.insert(make_pair(distanta[gr[nod_curent][i].first],gr[nod_curent][i].first));
                }
            }

        }
        ofstream scriere("dijkstra.out");
        for(auto &x:distanta)
            if(x!=999 && x!=0)
                scriere<<x<<" ";
        scriere.close();
    }

};
int main()
{
    graf test;
    test.dijkstra();
    return 0;
}