#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#define NMax 50005
#define CMax 50000005
#define oo 500005
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M;
vector < pair <int,int> > G[NMax];
list <int> L[CMax];
list <int> :: iterator A[NMax];
int D[NMax];

void Read()
{
	fin>>N>>M;
	for(int i=1;i<=M;i++)
    {
			int x,y,c;
			fin>>x>>y>>c;
			G[x].push_back(make_pair(y,c));
    }
}

void PrintLists()
{
    for(int i = 0 ; i <= oo ; i++)
    {
        cout<<"Lista lui "<<i<<" : ";
        for(list <int> :: iterator it = L[i].begin();it!=L[i].end();it++)
            cout<<*it<<" ";
        cout<<endl;
    }
    cout<<endl<<endl<<endl;
}

void Init()
{
	for(int i=2;i<=N;i++)
	{
		D[i]=oo;
		L[oo].push_back(i);
	}

	int Node=2;
	for(list <int> :: iterator it = L[oo].begin();it!=L[oo].end();it++)
		A[Node++]=it;

	L[0].push_back(1);
	A[1] = L[0].begin();

    PrintLists();
}

void Dijkstra()
{
		Init();
		for(int i = 0 ; i < oo; i++)
			{
      int Nod = L[i].front(); L[i].pop_front();
      for(unsigned int j = 0; j< G[Nod].size();j++)
				{
					int Vecin = G[Nod][j].first;
					int Cost  = G[Nod][j].second;
					if(D[Vecin] > D[Nod] + Cost)
						{
							L[D[Vecin]].erase(A[Vecin]);
							D[Vecin] = D[Nod] + Cost;
							L[D[Vecin]].push_back(Vecin);
							A[Vecin]=--L[D[Vecin]].end();
							PrintLists();
						}
				}
			}
}

void Print()
{
	for(int i=2;i<=N;i++)
		if(D[i]==oo)
			D[i]=0;
	for(int i=2;i<=N;i++)
		fout<<D[i]<<" ";
	fout<<"\n";
}

int main()
{
		Read();
		Dijkstra();
		Print();
    return 0;
}