#include <bits/stdc++.h>

using namespace std;

bool visit[51100];

int dist[51100],marime;

struct graph
{
    vector <int> nod;
    vector <int> cost;
} edge[250009];

struct djikstra
{
    int nod;
    int dist;
} v[250009];

void swaap (struct djikstra* a,struct djikstra* b)
{
    djikstra temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

int lg;

void upcheck (int node)
{
    if (v[node/2].dist>v[node].dist)
    {
        if (node/2>=1)
        {
            swaap(&v[node],&v[node/2]);
            upcheck(node/2);
        }
    }
}

void downcheck (int node)
{
    int wher=1;
    if ((node*2+1)<=marime)
    {
        if (v[node*2].dist<v[node*2+1].dist)
        {
            wher=0;
        }
        if (v[node*2+wher].dist<v[node].dist)
        {
            swaap(&v[node],&v[node*2+wher]);
            int val=node*2+wher;
            downcheck(val);
        }
    }
    else
    {
        if (2*node==marime)
        {
            if (v[2*node].dist<v[node].dist)
            {
                swaap(&v[node],&v[node*2]);
            }
        }
    }
}

void delet ()
{
    swaap(&v[1],&v[marime]);
    marime--;
    downcheck(1);
}

void Djikstra (int source)
{
    for (int i=0; i<=1110; ++i)
    {
        dist[i]=-1;
    }
    v[++marime].dist=0;
    v[marime].nod=source;
    //visit[source]=1;
    //*
    while (marime>0)
    {
        int nodul=v[1].nod;
        if (visit[nodul]==0)
        {
            visit[nodul]=1;
            dist[nodul]=v[1].dist;
            delet();
            for (int i=0; i<edge[nodul].nod.size(); ++i)
            {
                if (visit[edge[nodul].nod.at(i)]==0)
                {
                    v[++marime].dist=dist[nodul]+edge[nodul].cost.at(i);
                    v[marime].nod=edge[nodul].nod.at(i);
                    upcheck(marime);
                }
            }
        }
        else
        {
            while (visit[v[1].nod]==1 && marime)
            {
                delet();
            }
            if (marime>=1)
            {
                nodul=v[1].nod;
                visit[nodul]=1;
                dist[nodul]=v[1].dist;
                nodul=v[1].nod;
                delet();
                for (int i=0; i<edge[nodul].nod.size(); ++i)
                {
                    if (visit[edge[nodul].nod.at(i)]==0)
                    {
                        v[++marime].dist=dist[nodul]+edge[nodul].cost.at(i);
                        v[marime].nod=edge[nodul].nod.at(i);
                        upcheck(marime);
                    }
                }
            }
            visit[nodul]=1;
        }
    }
    //*/
}

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int n,m;
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int a,b,costul;
        fin>>a>>b>>costul;
        edge[a].nod.push_back(b);
        edge[a].cost.push_back(costul);
    }
    int a,b;
    //fin>>a>>b;
    Djikstra(1);
    for (int j=2;j<=n;++j)
    {
    fout<<dist[j]<<" ";
    }
    return 0;
}