#include<fstream>
#include<set>
#include<vector>
#include<string>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct dij{
	int nr, cost;
};

struct classcomp {
  bool operator() (const dij& lhs, const dij& rhs) const
  {return lhs.cost<rhs.cost;}
};

const int nmax = 50006, inf = 6000000;
int n, m, vcost[nmax];
vector<dij> vecini[nmax];
multiset <dij, classcomp> s;
bool poz[nmax];
string buffer;
string::iterator buffer_it;
	 
void dijkstra(int x)
{
	vcost[x] = 0;
	poz[x] = 1;

	for(int i = 0; i<(int)vecini[x].size(); i++)
	{
		dij aux;

		aux.nr = vecini[x][i].nr;
		aux.cost = vecini[x][i].cost;

		s.insert(aux);
	}

	while(s.empty()==0)
	{
		dij aux = *s.begin();

		if(poz[aux.nr]==0)
		{
			vcost[aux.nr] = aux.cost;
			poz[aux.nr] = 1;

			for(int i = 0; i<(int)vecini[aux.nr].size(); i++)
			{
				if(poz[vecini[aux.nr][i].nr]==0)
				{
					dij aux2;

					aux2.cost = aux.cost + vecini[aux.nr][i].cost;
					aux2.nr  = vecini[aux.nr][i].nr;

					s.insert(aux2);
				}
			}
		}

		s.erase(s.begin());
	}
}

void read_int_nn( int &x ) {
for ( ; *buffer_it>'9' || *buffer_it<'0'; ++buffer_it ) ;
for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
x= x*10+*buffer_it-'0';
}
}

int main(){
	int player_unu=0;

	getline(in, buffer, (char)0);
	buffer_it = buffer.begin();

	read_int_nn(n);
	read_int_nn(m);
	for(int i = 0; i<m; i++)
	{
		int x, y, cost;
		read_int_nn(x);
		read_int_nn(y);
		read_int_nn(cost);

		dij aux;
		aux.cost = cost;
		aux.nr = y;

		vecini[x].push_back(aux);
	}

	dijkstra(1);

	for(int i = 2; i<=n; i++)
	{
		if(vcost[i]==inf)
			out<<0<<' ';
		else
			out<<vcost[i]<<' ';
	}

	return player_unu;
}