#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX = 50005;
const int INF = 0x3f3f3f3f;
bitset<NMAX> inCoada;
queue<int> coada;
vector<int> cmin(NMAX, INF);
vector< pair<int,int> > cost[NMAX];
int N,M;
void Citire();
void BellmanFord();
void Afisare();
int main()
{
Citire();
BellmanFord();
Afisare();
return 0;
}
void Citire()
{
fin>>N>>M;
int x,y,cst,i;
for(i = 1; i <= M; i++)
{
fin>>x>>y>>cst;
cost[x].push_back(make_pair(y,cst));
}
fin.close();
}
void BellmanFord()
{
coada.push(1);
inCoada[1].flip();
cmin[1] = 0;
while (!coada.empty())
{
int x = coada.front();
coada.pop();
inCoada[x] = false;
vector < pair <int, int> >::iterator it;
for( it = cost[x].begin(); it != cost[x].end(); ++it)
if(cmin[x] + it->second < cmin[it->first])
{
cmin[it->first] = cmin[x] + it->second;
if(! inCoada[it->first])
{
coada.push(it->first);
inCoada[it->first] = true;
}
}
}
}
void Afisare()
{
int i;
for (i = 2; i <= N; ++i)
{
if(cmin[i]<INF)
fout << cmin[i] <<" ";
else
fout << "0 ";
}
fout<<'\n';
fout.close();
}