#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX=5e4;
vector<pair<int,int>> L[NMAX+1]; //vecin+ cost dintre nod si vecin
int n,m,d[NMAX+1],vis[NMAX+1];
void dijkstra(int s){
for(int i=1;i<=n;i++)
{
d[i]=1e9;
}
d[s]=0;
priority_queue<pair<int,int>> pq;
pq.push({-d[s],s});
while(pq.empty()==false)
{
int nod=pq.top().second;
pq.pop();
if(vis[nod]) continue;
vis[nod]=1;
for(auto it : L[nod])
{
int vecin=it.first;
int cost=it.second;
if(d[vecin]>d[nod]+cost)
{d[vecin]=d[nod]+cost;
pq.push({-d[vecin],vecin});}
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,c;
fin>>x>>y>>c;
L[x].push_back({y,c});
}
dijkstra(1);
for(int i=2;i<=n;i++)
{
if(d[i]==1e9)
d[i]=0;
fout<<d[i]<<" ";
}
return 0;
}