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

using namespace std;

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

const int NLIM = 50005;

int N,M,Start,Finish;
int Distanta[NLIM];
int vizitat[NLIM];
int distanta[NLIM];

vector <pair<int,int>> Graf[250002];
queue <int> Coada;

void Fill()
{
    for(int i=1; i <= N+10; i++) distanta[i] = INT_MAX;
}

void BFS(int Start)
{
    int Nod, Vecin;
    distanta[Start] = 0;
    Coada.push(Start);
    vizitat[Start] = 1;
    while(!Coada.empty())
    {
        Nod = Coada.front();
        Coada.pop();
        for(int i=0; i < Graf[Nod].size(); i++)
        {
            Vecin = Graf[Nod][i].first;
            if(!vizitat[Vecin])
            {
                Coada.push(Vecin);
                vizitat[Vecin] = 1;
                if(distanta[Vecin] > (distanta[Nod] + Graf[Nod][i].second))
                {
                    distanta[Vecin] = distanta[Nod] + Graf[Nod][i].second;
                }
                //cout<<distanta[Vecin]<<" ";
            }
            else if(distanta[Vecin] > (distanta[Nod] + Graf[Nod][i].second))
                {
                    Coada.push(Vecin);
                    distanta[Vecin] = distanta[Nod] + Graf[Nod][i].second;
                }
        }
    }
}

void Citire()
{
    fin>>N>>M;
    int x,y,d;
    for(int i = 1; i <= M; i++)
    {
        fin>>x>>y>>d;
        Graf[x].push_back(make_pair(y,d));
    }
}

void TerminareINTMAX()
{
    for(int i = 1; i <= N; i++)
    {
        if(distanta[i] == INT_MAX) distanta[i] = 0;
    }
}

int main()
{
    Citire();
    Fill();
    BFS(1);
    TerminareINTMAX();
    for(int i = 2; i <= N; i++) fout<<distanta[i]<<" ";
    return 0;
}