#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <limits>
#include <set>
#define mx 50000
const int inf=std::numeric_limits<int>::max();
using namespace std;

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

int n,m, sol[mx];
vector< pair<int,int> > adiacenta[mx]; //first nod || second cost
set< pair<int,int> > Mins;
void Read(), Write(), Dijkstra(), Initialize(), Relax(int,int,int);

void Dijkstra()
{
    Initialize();
    int NodCurent, CostCurent;
    for(;Mins.size();)
    {
        NodCurent=(*Mins.begin()).first;
        CostCurent=(*Mins.begin()).second;
        Mins.erase((*Mins.begin()));
        for(int i=0;i<adiacenta[NodCurent].size();++i)
        {
            Relax(NodCurent,adiacenta[NodCurent][i].first,adiacenta[NodCurent][i].second);
        }
    }
}

int main()
{
    Read();
    Dijkstra();
    Write();
    f.close();
    g.close();
    return 0;
}

inline void Relax(int sursa, int destinatie, int cost)
{
    if(sol[sursa]+cost<sol[destinatie])
    {
        sol[destinatie]=sol[sursa]+cost;
        Mins.insert(make_pair(destinatie, sol[destinatie]));
    }
}

inline void Initialize()
{
    for(int i=2;i<=n;++i)
        sol[i]=inf;

    Mins.insert(make_pair(1, 0));
}

void Read()
{
    f>>n>>m;
    int nod1, nod2, cost;
    for(int i=0;i<m;++i)
    {
        f>>nod1>>nod2>>cost;
        adiacenta[nod1].push_back(make_pair(nod2,cost));
    }
}

void Write()
{
    for(int i=2;i<=n;++i)
    {
        if(sol[i]==inf)
            g<0<<' ';
        else
            g<<sol[i]<<' ';
    }
}