#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

#define infinite 9999999
#define nmax 50005
using namespace std;

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

vector <vector <pair<int, int> > > gr;
int N;
int M;
priority_queue <pair <int, int> , vector <pair <int, int> >, greater <pair <int, int> > > prir;

int v[nmax];

void citire()
{
    f>>N>>M;
    int x;
    int y;
    int c;
    gr.resize(N+1);
    for(int i=0; i<M;i++)
    {
        f>>x>>y>>c;

        gr[x].push_back(make_pair(y,c));
    }

}
void afisare()
{
    for(int i=1;i<N+1;i++)
    {
        g<<i<<": ";
        for(int j=0;j<gr[i].size();j++)
        {
            g<<gr[i][j].first<<","<<gr[i][j].second<<"  ";
        }
        g<<"\n";
    }
}
void dijk(int x)
{
    prir.push(make_pair(0,x));


    for(int i=1;i<N+1;i++)
        v[i]=infinite;

    while(!prir.empty())
    {
        pair<int, int> prima=prir.top();
        prir.pop();
        if(v[prima.second]==infinite)
        {
            v[prima.second]=prima.first;
            for(int i=0;i<gr[prima.second].size();i++)
            {
                if(v[gr[prima.second][i].first] ==infinite)
                {
                    prir.push(make_pair(gr[prima.second][i].second+prima.first , gr[prima.second][i].first));
                }
            }
        }


    }
}

int main()
{
    citire();
    //afisare();
    dijk(1);

    for(int i=2;i<N+1;i++)
    {
        if(v[i]!=infinite)
            g<<v[i]<<" ";
        else
            g<<0<<" ";
    }

}