#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int american= 1 << 30;
vector<pair<int, int> > v[50001];
int n,m,cost[50001],viz[50001],nod;
void drum(int p);
int main()
{
ifstream mama("dijkstra.in");
ofstream tata("dijkstra.out");
int a,b,c,i;
mama>>n>>m;
for(i=0;i<m;i++)
{
mama>>a>>b>>c;
v[a].push_back(make_pair(b,c));
}
drum(1);
for(i=2;i<=n;i++)
tata<<cost[i]<<" ";
return 0;
}
void drum(int p)
{
int i;
for(i=2;i<=n;i++)
cost[i]=american;
cost[1]=0;
for(i=2;i<=n;i++)
viz[i]=0;
priority_queue< pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > r;
r.push(make_pair(0,1));
while(!r.empty())
{
nod=r.top().second;
r.pop();
if(viz[nod]==0) viz[nod]=1;
for(i=0;i<v[nod].size();i++)
{
if(cost[nod]+ v[nod][i].second < cost[v[nod][i].first])
{
cost[v[nod][i].first]=cost[nod]+v[nod][i].second;
r.push(make_pair(cost[v[nod][i].first],v[nod][i].first));
}
}
}
}