#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>
#include <functional>
#include <cstring>
#include <set>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define INF 50000000
const int N=50000, M=250000;
vector<pair<int,int>> ad[N+1];
int n, m, d[N+1], a, b, c;
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
fin>>a>>b>>c;
ad[a].push_back(make_pair(b, c));
}
fill_n(d, n+1, INF);
d[1] = 0;
set<pair<int,int>> pq;
pq.insert(make_pair(0, 1));
while(!pq.empty())
{
int p = pq.begin()->second;
pq.erase(pq.begin());
for(auto x : ad[p])
{
if (d[p]+x.second<d[x.first])
{
if(d[x.first] != INF)
pq.erase(pq.find(make_pair(d[x.first], x.first)));
d[x.first]=d[p]+x.second;
pq.insert(make_pair(d[x.first], x.first));
}
}
}
for(int i=2;i<=n;i++)
fout<<((d[i]==INF)?0:d[i])<<" ";
return 0;
}