#include <fstream>
#include <vector>
#include <set>
#include <iostream>
#define MX 50000
#define inf 1000
using namespace std;

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

int n, m, d[MX];
vector<int> Vecin[MX], Cost[MX];
set<pair<int,int> > DeR;// first== NOD second==COST
void Read(), Solve(), Write(), Initialize(), Relax(int, int, int);


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

void Solve()
{
    int nod, cost;
    Initialize();
    for(;DeR.size();)
    {
        nod = (*DeR.begin()).first;
        cost= (*DeR.begin()).second;
        DeR.erase(*DeR.begin());
        for(int i=0;i<Vecin[nod].size();++i)
        {
            Relax(nod, cost, i);
        }

    }
}

void Relax(int n, int c, int i)
{
    if(d[Vecin[n][i]]> c+Cost[n][i])
    {
        d[Vecin[n][i]]= c+Cost[n][i];
        DeR.insert(make_pair(Vecin[n][i], d[Vecin[n][i]]));
    }
}

void Initialize()
{
    d[0]=0;
    for(int i=2;i<=n;++i)
    {
        d[i]=inf;
    }
    DeR.insert(make_pair(1,0));
}

void Read()
{
   f>>n>>m;
   for(int i=1;i<=m;i++)
        {
            int I,J,W;
            f>>I>>J>>W;
            Vecin[I].push_back(J);
            Cost[I].push_back(W);
        }
}

void Write()
{
    for(int i=2;i<=n;++i)
    {
        g<<((d[i]==inf) ? 0 : d[i])<<' ';
    }
}