#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector< pair <int,int> > v[50005];
const int inf=1<<30;
int cost[50005];
int n,m;
priority_queue < pair < int ,int > ,vector < pair <int,int> >
 , greater <pair <int ,int > > > H;

int main()
{in>>n>>m;
int x,y,i,c;
for(i=1;i<=n;i++)
    cost[i]=inf;
for(i=1;i<=m;i++)
{
    in>>x>>y>>c;
    v[x].push_back(make_pair(y,c));
}
H.push(make_pair(0,1));
cost[1]=0;
while(H.size())
{
    int cc=H.top().first;
    int nod=H.top().second;
    H.pop();
    if(cc>cost[nod])
        continue;
    for(int j=0;j<v[nod].size();j++)
    {
        if(cost[v[nod][j].first]>cc+v[nod][j].second)
        {
            cost[v[nod][j].first]=cc+v[nod][j].second;
            H.push(make_pair(cc+v[nod][j].second,v[nod][j].first));
        }
    }
}
for(i=2;i<=n;i++)
{
    if(cost[i]==inf)
        out<<0<<" ";
    else
        out<<cost[i]<<" ";
}
    return 0;
}