#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

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

/*struct muchie
{
    int nod1, nod2, cost;
    friend bool operator < (vecin a, vecin b)
    {
        return a.cost > b.cost;
    }
};*/

struct vecin
{
    int nod, cost;
    friend bool operator < (vecin a, vecin b)
    {
        return a.cost > b.cost;
    }
};

void citire_la(vector <vecin> la[], int m)
{
    int a;
    vecin x;
    for(int i = 1; i <= m; i++)
    {
        fin >> a >> x.nod >> x.cost;

        la[a].push_back(x);
    }
}

void afisare_la(vector <vecin> la[], int n)
{
    for(int i = 1; i <= n; i++)
    {
        fout << i << ": ";
        for(int j = 0; j < la[i].size(); j++)
            fout << "(" << la[i][j].nod << "," << la[i][j].cost << "), ";
        fout << '\n';
    }
}

priority_queue <vecin> et;
int tata[NMAX], d[NMAX];

void dijkstra(vector <vecin> la[], int n)
{
    vecin a, b;
    for(int i = 2; i <= n; i++)
        d[i] = INT_MAX;
    a.nod = 1;
    a.cost = 0;
    et.push(a);
    d[1] = 0;
    while(!et.empty())
    {
        a = et.top();
        for(int i = 0; i < la[a.nod].size(); i++)
        {
            if((d[a.nod]+la[a.nod][i].cost)<d[la[a.nod][i].nod])
            {
                d[la[a.nod][i].nod] = d[a.nod]+la[a.nod][i].cost;
                tata[la[a.nod][i].nod] = a.nod;
                b.nod = la[a.nod][i].nod;
                b.cost = d[la[a.nod][i].nod];
                et.push(b);
            }
        }
        et.pop();
    }
}

int main()
{
    int n, m;
    vector <vecin> la[1000];
    fin >> n >> m;
    citire_la(la, m);
    //afisare_la(la, n);
    dijkstra(la, n);
    for(int i = 2; i <= n; i++)
    {
        fout << d[i] << " ";
    }
    return 0;
}