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

#define NMAX 50005
#define oo (1<<31 - 1)

using namespace std;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
long n,m;
long D[NMAX];
bool InCoada[NMAX];
vector <pair<long,long> > G[NMAX];

struct compara {
    bool operator()(long x, long y){
        return D[x]>D[y];
    }
};

priority_queue < long, vector<long>, compara > Coada;

void citire()
{
    long x,y,c;
    f>>n>>m;
    for(long i=0;i<m;i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}

void dijkstra(long nodStart)
{
    for(long i=1;i<=n;i++)
    {
        D[i] = oo;
        InCoada[i] = false;
    }
    D[nodStart] = 0;
    InCoada[nodStart] = true;
    Coada.push(nodStart);

    while(!Coada.empty())
    {
        long nodCurent = Coada.top();
        Coada.pop();

        for(size_t i=0 ; i < G[nodCurent].size(); i++)
        {
            long Vecin = G[nodCurent][i].first;
            long Cost = G[nodCurent][i].second;
            if(D[nodCurent] + Cost < D[Vecin])
            {
                D[Vecin] = D[nodCurent] + Cost;
                if(InCoada[Vecin] == false)
                {
                    InCoada[Vecin] = true;
                    Coada.push(Vecin);
                }
            }
        }
    }
}

void afisare()
{
    for(long i=2;i<=n;i++)
    {
        if(D[i]!= oo)
            g<<D[i]<<" ";
        else g<<"0 ";
    }
}

int main()
{
citire();
dijkstra(1);
afisare();
return 0;
}