#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));

	std::vector<int>tata(n+1);
	for(int i=1;i<n+1;i++)
    {
        tata[i]=i;
    }
	while(!s.empty())
	{
		int ind=(*s.begin()).second;
		for(auto muchie:graf[ind])
		{
			if(distanta[muchie.nod]>distanta[ind]+muchie.cost )
			{
				s.erase(std::make_pair(distanta[muchie.nod],muchie.nod));

                //if(muchie.nod==6)
                    //std::cout<<tata[muchie.nod]<<' '<<distanta[muchie.nod]<<'\n';


				tata[muchie.nod]=ind;
				distanta[muchie.nod]=distanta[ind]+muchie.cost;

				s.insert(std::make_pair(distanta[muchie.nod],muchie.nod));


                //if(muchie.nod==6)
                    //std::cout<<tata[muchie.nod]<<' '<<distanta[muchie.nod]<<'\n';
			}

        }

        s.erase(s.begin());

	}


	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);



}