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

using namespace std;

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

const int NMAX = 50005;
const int NEVIZITAT = -1;


vector< pair<int, int> > G[NMAX];
int costuri[NMAX];

long long N,M;

void read()
{
    fin>>N>>M;
    for(unsigned int i = 1; i<=M; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    for(long long i = 1; i<NMAX; i++)
        costuri[i] = NEVIZITAT;
}

void dijkstra()
{
    queue<int> coada;
    costuri[1] = 0;
    coada.push(1);
    while( !coada.empty() )
    {
        int n = coada.front();
        coada.pop();
        for(unsigned int i = 0; i < G[n].size(); i++)
        {
            pair<int,int> vecin = G[n].at(i);
            if( (costuri[n] + vecin.second < costuri[vecin.first]) || costuri[vecin.first] == NEVIZITAT )
            {
                costuri[vecin.first] = costuri[n] + vecin.second;
                coada.push(vecin.first);
            }
        }
    }
    for(int i = 2; i <= N; i++)
    {
        if(costuri[i] != NEVIZITAT)
            fout<<costuri[i]<<' ';
        else
            fout<<'0'<<' ';
    }
}

int main()
{

    read();
    dijkstra();
    return 0;
}