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


std::vector<std::vector<Muchie> > construieste(std::vector<int>&tata,std::vector<int>&distanta,int n)
{

    std::vector<std::vector<Muchie> >drum(n+1);
    for(int i=1;i<n+1;i++)
    {
        if(i==tata[i])
            continue;

        drum[i].push_back(Muchie{tata[i],distanta[i]-distanta[tata[i]]});
        drum[tata[i]].push_back(Muchie{i,distanta[i]-distanta[tata[i]]});

    }

    return drum;
}

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


	std::vector<int>distanta(n+1,1000);
	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;
    }
	for (int i = 0; i < n; ++i)
	{
		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));

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

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


			}

        }

        s.erase(s.begin());
        if(s.empty())
        	break;
	}

	std::ofstream fout("dijkstra.out");
	for(unsigned i=2;i<n+1;i++)
        fout<<distanta[i]<<' ';

///	return construieste(tata,distanta,n);
}







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});
		graf[b].push_back(Muchie{a,cost});
	}





	///std::vector<std::vector<Muchie> >drum=
	dijkstra(graf,1,n);






	return 0;
}