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

#define pb push_back
#define mk make_pair
using namespace std;

const int maxn=50004;
const int inf=100000;

vector <pair<int, int> >v[maxn];
queue <int>q;
bitset<maxn>viz;

int dmin[maxn],n,m;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void citire()
{int i, a,b,c;

f>>n>>m;

for(i=0;i<m;i++)
{
f>>a>>b>>c;

v[a].pb(mk(b,c));
}


}


void dijkstra()
{
 int i, nod;
 
 for(i=0;i<=maxn;i++)
 {
 viz[i]=0;
 dmin[i]=inf;
 }

 dmin[1]=0;
 viz[1]=1;
 q.push(1);
 while(!q.empty())
 {
 nod=q.front();
 q.pop();
 viz[nod]=0;
 for(vector<pair< int, int > >::iterator it=v[nod].begin();it!=v[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]=1;
		   
	  }
	}
  }
}

int main()
{int i;
	citire();
	dijkstra();
	for(i=2;i<=n;i++)
		g<<(dmin[i]<inf?dmin[i]:0)<<" ";
g<<"da";
return 0;
}