#include <bits/stdc++.h>
using namespace std;
const int MAX=50001;
const int INF=200001;
vector<pair<int,int> >graf[MAX*2];
priority_queue<pair<int,int > >h;
bool sel[MAX];
int n,m,st,dr,cost,d[MAX];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void dijkstra(int start)
{
    int x,c,y;
    for(int i=1;i<=n;i++) d[i]=INF;
    d[start]=0;
    h.push(make_pair(-d[start],start));
    while(!h.empty())
    {
    while(!h.empty() && sel[h.top().second]) h.pop();
    if(h.empty()) return;
    x=h.top().second;
    h.pop();
    sel[x]=true;
    for(int i=0;i<graf[x].size();i++)
    {
        pair<int,int> p=graf[x][i];
        y=p.second;
        c=p.first;
        if(d[x]+c<d[y])
        {
            d[y]=d[x]+c;
            //sel[y]=true;
            h.push(make_pair(-d[y],y));
        }
    }
}
}
int main()
{
    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        in>>st>>dr>>cost;
        graf[st].push_back(make_pair(cost,dr));
    }

    dijkstra(1);

    for(int i=2;i<=n;i++)
    { if(d[i]!=INF) out<<d[i]<<" ";
     else out<<"0 ";
    }
    return 0;
}