#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1000000000
#define NMAX 50001

using namespace std;

int n, x0;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX]; //distantele minime
//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;

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, vfmin;
 for (i=1; i<=n; i++) dmin[i]=INF; //prec[i]=x0;}
 dmin[x0]=0; //prec[x0]=-1;
 H.push(x0);
 while (!H.empty())
	  {
	   vfmin=H.top(); H.pop();
	   if (!M[vfmin]) //vfmin nu a mai fost selectat
           {
	        M[vfmin]=true;
	        for (i=0; i<G[vfmin].size(); i++)
	            //parcurg lista de adiacenta a lui vfmin
			    if (!M[G[vfmin][i].first]) //nu a fost deja selectat
				    if (dmin[G[vfmin][i].first]>dmin[vfmin]+G[vfmin][i].second) //obtin ceva mai bun
					   {
					    dmin[G[vfmin][i].first]=dmin[vfmin]+G[vfmin][i].second;
					    //prec[G[vfmin][i].first]=vfmin;
					    H.push(G[vfmin][i].first);
					    }
       }
	}
}


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);
}