#include <iostream>
#include <fstream>
#include <vector>

//std::ifstream fin("date.in");
std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

struct vertex
{
	int index, cost;
	vertex *next;
};
vertex *liste[60005];

int n, m, a[100][100], v[60005], costMinim[60005];

void citireMatrice()
{
	int i, j;
	fin>>n>>m;
	while(fin>>i>>j)
	{
		a[i][j] = a[j][i] = 1;
	}
}

void dfMatrice(int k)
{
	for(int i = 1 ; i <= n ; i++)
	{
		if(a[i][k] == 1 && !v[i])
		{
			std::cout<<i<<" ";
			v[i] = 1;
			dfMatrice(i);
		}
	}
}

void bfMatrice(int k)
{
	std::vector<int> vec;
	vec.push_back(k);

	while(vec.size())
	{
		for(int i = 1 ; i <= n ; i ++)
		{
			if(a[vec.front()][i] == 1 && !v[i])
			{
				a[vec.front()][i] = a[i][vec.front()] = 2;
				std::cout<<i<<' ';
				v[i] = 1;
				vec.push_back(i);
			}
		}
		vec.erase(vec.begin());
	}
}


void citireListe()
{
	int x, y;
	fin>>n>>m;
	for(int i = 1; i <= m ; i++)
	{
		fin>>x>>y;
		vertex *newVex = new vertex;
		newVex->index = y;
		newVex->next = liste[x];
		liste[x] = newVex;

		vertex *newVex2 = new vertex;
		newVex2->index = x;
		newVex2->next = liste[y];
		liste[y] = newVex2;
	}
}

void dfListe(int k)
{
	vertex *p = liste[k];
	while(p)
	{
		if(!v[p->index])
		{
			//std::cout<<p->index<<" ";
			v[p->index] = 1;
			dfListe(p->index);
		}
		p = p->next;
	}
	delete p;
}

void bfListe(int k)
{
	std::vector<int> vec;
	vec.push_back(k);

	while(vec.size())
	{
		vertex *p = liste[vec.front()];
		while(p)
		{
			if(!v[p->index])
			{
				v[p->index] = 1;
				vec.push_back(p->index);
				std::cout<<p->index<<" ";
			}
			p = p->next;
		}
		delete p;
		vec.erase(vec.begin());
	}
}




void bfDijsktra(int k)
{
	std::vector<int> vec;
	vec.push_back(k);

	while(vec.size())
	{
		vertex *p = liste[vec.front()];
//		std::cout<<"         "<<vec.front()<<'\n';
		if(p)
		{
			int lastCost = costMinim[vec.front()];
			while(p)
			{
				if(costMinim[p->index] < 0)
				{
					costMinim[p->index] = p->cost + lastCost;
					vec.push_back(p->index);
				}
				else
					if(costMinim[p->index] >= 0)
					{
						if(costMinim[p->index] > p->cost + lastCost)
						{
							costMinim[p->index] = p->cost + lastCost;
							vec.push_back(p->index);
						}
					}
//				std::cout<<vec.front()<<": "<<p->index<<" "<<costMinim[p->index]<<'\n';

				p = p->next;
			}
//			std::cout<<"pula"<<'\n';
		}
		delete p;
		vec.erase(vec.begin());
	}
}


void citireDijsktra()
{
	fin>>n>>m;
	int x,y,c;

	for(int i = 1 ; i <= n; i++)
	{
		costMinim[i] = -1;
		liste[i] = NULL;
	}
	costMinim[1] = 0;

	for(int i = 1; i <= m; i++)
	{
		fin>>x>>y>>c;

		vertex *newVex = new vertex;
		newVex->index = y;
		newVex->cost = c;
		newVex->next = liste[x];
		liste[x] = newVex;
	}

//	for(int i = 1 ; i <= n ; i++)
//	{
//		vertex *p = liste[i];
//		std::cout<<i<<": ";
//		while(p)
//		{
//			std::cout<<p->index<<" "<<p->cost<<"; ";
//			p = p->next;
//		}
//		std::cout<<'\n';
//	}

}

void dijsktra()
{
	for(int i = 2; i <= n ; i++)
	{
		//std::cout<<costMinim[i]<<' ';
		if(costMinim[i] >= 0)
		{
			fout<<costMinim[i]<<' ';
		}
		else
		{
			fout<<"0 ";
		}
	}
}

int main()
{
	/*
	citireListe();
	std::cout<<1<<" ";
	v[1] = 1;
	bfListe(1);*/

	/*DFS infoarena*************
	citireListe();
	int nrTot = 0;
	for(int i = 1; i <= n ; i++)
	{
		if(!v[i])
		{
			nrTot++;
			dfListe(i);
		}
	}***************************/
	///fout<<nrTot;
/*
	std::cout<<'\n'<<'\n';
	for(int i = 1; i <= n ;i++)
	{
		std::cout<<i<<": ";
		vertex *p = liste[i];
		while(p)
		{
			std::cout<<p->index<<" ";
			p = p->next;
		}
		delete p;
		std::cout<<'\n';
	}*/
	citireDijsktra();
	bfDijsktra(1);
	dijsktra();
    //cout << "Hello world!" << '\n';
    return 0;
}