#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int oo = 50001, Nmax = 50005;
int n, m, D[Nmax];
vector < pair<int ,int> > G[Nmax];
list <int> L[Nmax];
list <int> :: iterator A[Nmax];

void Read()
{
    f>>n>>m;
    for(int i = 1;i <= m;i++)
    {
            int a,b,c;
            f>>a>>b>>c;
            G[a].push_back(make_pair(b,c));
    }
}

void Init()
{
    for(int i = 2; i <= n; i++)
    {
        D[i] = oo;
        L[oo].push_back(i);
    }

    int Node=2;
    for(list <int> :: iterator it = L[oo].begin();it!=L[oo].end();it++)
        A[Node++]=it;

    L[0].push_back(1);
    A[1] = L[0].begin();
}

void Solve()
{
    Init();
    for(int i = 0; i < oo; i++)
    {
        while(!L[i].empty())
        {
            int nod = L[i].front(); L[i].pop_front();
            for(int j = 0; j < (int)G[nod].size(); j++)
            {
                int vecin = G[nod][j].first;
                int cost = G[nod][j].second;
                if(D[vecin] > D[nod]+cost)
                {
                    L[D[vecin]].erase(A[vecin]);
                    D[vecin] = D[nod] + cost;
                    L[D[vecin]].push_back(vecin);
                    A[vecin] = --L[D[vecin]].end();
                }
            }
        }
    }
}

void Print()
{
    for(int i = 2; i <= n; i++)
    {
        if(D[i] == oo) g<<0<<' ';
        else g<<D[i]<<' ';
    }
    g<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}