#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>

const int maxn =50005;
const int inf=1000000;
using namespace std;
int n,m;
vector<pair<int, int> >G[maxn];
int dmin[maxn];

void citire()
{
     int i;
ifstream f("dijkstra.in");
f>>n>>m;
int a,b,c;
for(i=0;i<m;++i)
  {
   f>>a>>b>>c;
   G[a].push_back(make_pair(b,c));
   
}
void dijks()
{
bool viz[maxn];
queue<int>Q;
int i; 
for(i=0;i<=maxn;i++)
{
dmin[i]=inf;
viz[i]=false;
}
     dmin[1]=0;
     Q.push(1);
     viz[1]=true;
     while(!Q.empty())
     {
     int nod=Q.front();
     Q.pop();
     viz[nod]=false;
     for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if (Dmin[nod] + it->second < Dmin[it->first]) {
				Dmin[it->first] = Dmin[nod] + it->second;
				if (!viz[it->first]) {
					Q.push(it->first);
					viz[it->first] = true;
				}
			}
	}
}

void afisez()
{
     int i;
  ofstream g("dijkstra.out");
  
     for(i=2;i<=n;++i)
     g<<(dmin[i]<inf ? dmin[i]: 0)<<" ";
    
}

int main()
{
citire();
dijks();
afisez();  
}