#include<fstream>
#include<vector>
#include<queue>
#define inf 10000000
#define NMAX 50005
using namespace std;
typedef vector<long> LI;
typedef LI::iterator IT;
LI a[NMAX],c[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(y);
     c[x].push_back(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(),p=c[k].begin();it!=a[k].end();++it,++p)
     if(d[*it]>d[k]+*p)
		{d[*it]=d[k]+*p;
	     if(v[*it]==0)
		 {q.push(*it);
		  v[*it]=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;
}