#include <bits/stdc++.h>

using namespace std;

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

const int N = 50005;
const int oo = 1e9;
bool viz[N];
vector<pair<int,int>>a[N];

int n,m,d[N];

void citire()
{
    int x,y,c;
    in >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        in >> x >> y >> c;
        a[x].push_back(make_pair(y,c));
    }
}

struct cmp
{
    bool operator()(int x,int y)
    {
        d[x] > d[y];
    }
};

priority_queue <int,vector<int>,cmp> Q; ///sortezi nordurile din heap dupa distanta

void dijkstra()
{
    int i,nod,vecin,cost;
    for(i = 2; i <= n; i++)
        d[i] = oo;
    d[1] = 0;
    Q.push(1);
    viz[1] = 1;
    while(!Q.empty())
    {
        nod = Q.top();
        viz[nod] = 0;
        Q.pop();
        for(i = 0; i < (int)a[nod].size(); i++)
        {
            vecin = a[nod][i].first;
            cost = a[nod][i].second;
            if(d[vecin] > d[nod] + cost)
            {
                d[vecin] = d[nod] + cost;
                if(viz[vecin] == 0)
                {
                    viz[vecin] = 1;
                    Q.push(vecin);
                }
            }
        }
    }
}


int main()
{
    citire();
    dijkstra();
    for(int i = 2; i <= n ; i++)
        out << d[i] << " ";
    return 0;
}