#include <bits/stdc++.h>

using namespace std;
const int MAX=100005;
const int INF=2e5;

int n,m,x,y,c,st,dr,cost;
bool sel[MAX];
int d[MAX];

vector<pair<int,int> >graf[MAX];

priority_queue<pair<int,int> >h;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void dijkstra(int start)
{
    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;
                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;
}