#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n,m;
int a,b,c;
int viz[NMAX];
int D[NMAX];

vector<pair <int , int > > vec[NMAX];

struct compar
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};

priority_queue<int , vector<int> , compar > coada;

void dij(int start)
{
    for (int i=1; i<=n; i++)
        D[i] = INT_MAX;
    D[start] = 0;

    coada.push(start);
    viz[start] = 1;

    while(!coada.empty())
    {
        int nod_curent = coada.top();

        coada.pop();

        for (size_t i=0; i<vec[nod_curent].size(); i++)
        {
            int vecin = vec[nod_curent][i].first;
            int cost = vec[nod_curent][i].second;

            if (D[vecin] > D[nod_curent] + cost)
            {
                D[vecin] = D[nod_curent] + cost;

                if (viz[vecin] < n - 1)
                {
                    coada.push(vecin);
                    viz[vecin]++;
                }
            }
        }
    }
}
void afisare()
{
    for (int i=2; i<=n; i++)
    {
        if (D[i] == INT_MAX)
            fout<<0<<" ";
        else
            fout<<D[i]<<" ";
    }
    fout<<"\n";
    fin.close();
    fout.close();
}
void citire()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        vec[a].push_back(make_pair(b,c));
    }

    dij(1);
    afisare();

}
int main()
{
    citire();
    return 0;
}