#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 2000000000
#define NMAX 50001

using namespace std;

int n, x0;
vector <vector < pair<int,int> > > G(NMAX);
vector<int>  dmin(NMAX, INF); //distantele minime
//vector<int>  prec (NMAX); //pot reconstitui drumul
vector<bool> M(NMAX, false); //multimea varfurilor selectate
//vector<int> poz(NMAX, -1); //poz[i]=-1 daca vf i nu a fost pus in heap, respectiv pozitia nodului i in heap

vector<int> H;

class ComparVf
{public:
 bool operator () (const int& x, const int& y)
 { return dmin[x]>dmin[y]; }
};

void citire();
void dijkstra();
void afisare();

int main()
{
 citire();
 dijkstra();
 afisare();
 return 0;
}


void citire()
{int i, m, x, y, c;
 FILE * fin=fopen("dijkstra.in","r");
 fscanf(fin,"%d %d", &n, &m); x0=1;
 for (i=0; i<m; i++)
     { fscanf(fin,"%d %d %d", &x, &y, &c);
       G[x].push_back(make_pair(y,c)); }
}

void dijkstra()
{int i, nrs=0, j, vfmin;
 vector<int>::iterator it;
 //for (i=1; i<=n; i++) prec[i]=x0;
 dmin[x0]=0; //prec[x0]=-1;

 H.push_back(x0); push_heap(H.begin(), H.end(), ComparVf());
 while (nrs<n) //nu au fost selectate toate varfurile
	  {if (H.empty()) break;
	   vfmin=H.front();
	   pop_heap(H.begin(), H.end(), ComparVf());
	   H.pop_back();
	   M[vfmin]=true; nrs++;
	   for (j=0; j<G[vfmin].size(); j++)
			if (!M[G[vfmin][j].first]) //nu a fost deja selectat
				if (dmin[G[vfmin][j].first]>dmin[vfmin]+G[vfmin][j].second) //obtin ceva mai bun
					{
				    dmin[G[vfmin][j].first]=dmin[vfmin]+G[vfmin][j].second;
					//prec[G[vfmin][j].first]=vfmin;
					it=find(H.begin(), H.end(), G[vfmin][j].first);
					if (it==H.end())//nu e in heap
					    {H.push_back(G[vfmin][j].first);
					     push_heap(H.begin(), H.end(), ComparVf());}
						else //restaurez
						{push_heap(H.begin(), it, ComparVf());}
					}
	}
}


void afisare()
{
FILE * fout=fopen("dijkstra.out","w");
int i;
for (i=1; i<=n; i++)
	if (i!=x0)
		if (dmin[i]!=INF) fprintf(fout,"%d ",dmin[i]);
			else
			fprintf(fout,"0 ");
fclose(fout);
}