#include<fstream.h>
#include<map>
#include<list>
#define NMAX 50005
#define mp make_pair
#define inf 10000000
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
map<long,long> s;
LI a[NMAX],c[NMAX];
long v[NMAX],d[NMAX],n,m;
void cit()
{long i,x,y,cost;
  ifstream fin("dijkstra.in");
   fin>>n>>m;
    for(i=1;i<=m;++i)
	{fin>>x>>y>>cost;
	 a[x].push_back(y);
     c[x].push_back(cost);
	}
 fin.close();
}
void solve()
{long x,i,j,v;
 IT it,p;
 multimap<long,long>::iterator q;
 for(i=2;i<=n;++i)
	 d[i]=inf;
	 s.insert(mp(0,1));
  for(i=1;i<=n-1;++i)
	{q=s.begin();x=q->second;v=q->first;
     s.erase(q);
	  for(it=a[x].begin(),p=c[x].begin();it!=a[x].end();++it,++p)
		  if(d[*it]>v+*p)
		   d[*it]=v+*p,s.insert(mp(d[*it],*it));
	}
}
int main()
{cit();
 solve();
 ofstream fout("dijkstra.out");
 long i;
  for(i=2;i<=n;++i)
	  if(d[i]==inf)
		  fout<<0<<" ";
	  else
		  fout<<d[i]<<" ";
 fout.close();
 return 0;
}