#include<fstream>
#include<vector>
#include<queue>
#define mp make_pair
#define inf 10000000
#define NMAX 50005
using namespace std;
typedef vector< pair<long,long> > LI;
typedef LI::iterator IT;
LI a[NMAX];
long n,m,d[NMAX],v[NMAX];
queue<long> q;
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(mp(y,cost));
	}
 fin.close();
}
void solve()
{IT it,p;
 long k;
 for(k=2;k<=n;++k)
	 d[k]=inf;
 q.push(1);
 v[1]=0;
  while(!q.empty())
  {k=q.front();
   v[k]=0;
    for(it=a[k].begin();it!=a[k].end();++it)
     if(d[(*it).first]>d[k]+(*it).second)
		{d[(*it).first]=d[k]+(*it).second;
	     if(v[(*it).first]==0)
		 {q.push((*it).first);
		  v[(*it).first]=1;
		 }
		}
   q.pop();		
  }
}
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;
}