#include <cstdio>
#include <vector>
#include <queue>
#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

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

priority_queue<int,vector<int>, ComparVf> H;
//vector<bool> inH(NMAX, false);

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(x0); //inH[x0]=true;
 while (nrs<n) //nu au fost selectate toate varfurile
	  {if (H.empty()) break;
	   vfmin=H.top(); H.pop();
	   if (M[vfmin]) continue;
	   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;
					H.push(G[vfmin][j].first);
					//inH[G[vfmin][j].first]=true;
					}
	}
}


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