#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#include <limits.h>
struct Muchie
{
	int nod,cost;
};


void dijkstra(std::vector<std::vector<Muchie> >&graf,int sursa,int n)
{


	std::vector<int>distanta(n+1,INT_MAX);
	std::set<std::pair<int,int> >s;
    distanta[sursa]=0;

	s.insert(std::make_pair(0,sursa));

	while(!s.empty())
	{
		int ind=(*s.begin()).second;
		s.erase(s.begin());

		for(auto muchie:graf[ind])
		{
			if(distanta[muchie.nod]>distanta[ind]+muchie.cost )
			{
				s.erase(std::make_pair(distanta[muchie.nod],muchie.nod));
				distanta[muchie.nod]=distanta[ind]+muchie.cost;
				s.insert(std::make_pair(distanta[muchie.nod],muchie.nod));



			}

        }


	}




	std::ofstream fout("dijkstra.out");
	for(int i=2;i<n+1;i++)
        if(distanta[i]==INT_MAX)
            fout<<0<<' ';
        else
            fout<<distanta[i]<<' ';

}







int main(int argc, char const *argv[])
{

    std::ifstream fin("dijkstra.in");
	int n,m;
	fin>>n>>m;

	std::vector<std::vector<Muchie> > graf(n+1);
	for (int i = 0; i < m; ++i)
	{
		int a,b,cost;
        fin>>a>>b>>cost;
		graf[a].push_back(Muchie{b,cost});

	}


    dijkstra(graf,1,n);



}