#include<fstream.h>
#include<list>
#define inf 100000000
#define NMAX 50005
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI a[NMAX],c[NMAX];
long n,m,d[NMAX],v[NMAX];
void cit()
{ifstream fin("dijkstra.in");
  fin>>n>>m;
  long i,x,y,ct;
   for(i=1;i<=m;++i)
   {fin>>x>>y>>ct;
    a[x].push_back(y);
	c[x].push_back(ct);
   }
 fin.close();
}
void solve()
{long i,j,min,vfmin;
 v[1]=1;
 IT it,q;
 for(i=2;i<=n;++i)
	 d[i]=inf;
 for(it=a[1].begin(),q=c[1].begin();it!=a[1].end();++it,++q)
	 d[*it]=*q;
 for(i=1;i<=n-1;++i)
	 {min=inf;
	  for(j=1;j<=n;++j)
		 if(v[j]==0&&min>d[j])
		 {min=d[j];
		  vfmin=j;
		 }
	 v[vfmin]=1;
	 for(it=a[vfmin].begin(),q=c[vfmin].begin();it!=a[vfmin].end();++it,++q)
		 if(d[*it]>d[vfmin]+*q)
			 d[*it]=d[vfmin]+*q;
	 }
}
void afis()
{ofstream fout("dijkstra.out");
  long i;
  for(i=1;i<=n;++i)
	  if(d[i]==inf)
		  d[i]=0;
   for(i=2;i<=n;++i)
	   fout<<d[i]<<" ";
    fout<<'\n';
 fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}