#include <bits/stdc++.h>

using namespace std;

struct graf
{
    vector <int> nod;
    vector <int> cost;
}g[50009];

struct heap
{
    int cnod,val;
}v[500009];

int lg,dist[500009],n,m;

void swaap (heap &a,heap &b)
{
    heap temp;
    temp=a;
    a=b;
    b=temp;
}

void up (int pos)
{
    if (pos == 1)
    {
        return;
    }
    if (v[pos/2].val > v[pos].val)
    {
        swaap(v[pos/2],v[pos]);
        up(pos/2);
    }
}

void down (int pos)
{
    int bst=pos*2;
    if (bst > lg)
    {
        return;
    }
    if (bst < lg)
    {
        if (v[bst].val > v[bst+1].val)
        {
            bst++;
        }
    }
    if (v[bst].val < v[pos].val)
    {
        swaap(v[bst],v[pos]);
        down(bst);
    }
}

void remov()
{
    if (lg==1)
    {
        lg=0;
        return;
    }
    swaap(v[1],v[lg]);
    lg--;
    down(1);
}

void add (int nod,int ccost)
{
    lg++;
    v[lg].cnod=nod;
    v[lg].val=ccost;
    up(lg);
}

void dijkstra (int strt)
{
    add(1,0);
    while (lg)
    {
        //cout<<"aaa";
        int cnod=v[1].cnod,cost=v[1].val;
        //cout<<cnod<<" "<<dist[cnod]<<" "<<cost<<"<\n";
        remov();
        while (dist[cnod]!=-1 && lg)
        {
        //cout<<cnod<<" "<<dist[cnod]<<"\n";
        cnod=v[1].cnod;
        cost=v[1].val;
        remov();
        }
        if (!lg && dist[cnod]!=-1)
        {
            break;
        }
        if (dist[cnod]==-1)
        {
            dist[cnod]=cost;
        }
        //cout<<cnod<<"\n";
        for (int i=0;i<g[cnod].nod.size();++i)
        {
            if (dist[g[cnod].nod.at(i)]==-1)
            {
                //cout<<g[cnod].nod.at(i)<<"< ";
                add(g[cnod].nod.at(i),cost+g[cnod].cost.at(i));
            }
        }
        //cout<<"\n";
    }
}

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        int u,v,val;
        fin>>u>>v>>val;
        g[u].nod.push_back(v);
        g[u].cost.push_back(val);
    }
    for (int i=0;i<=n;++i)
    {
        dist[i]=-1;
    }
    dijkstra(1);
    for (int i=2;i<=n;++i)
    {
        if (dist[i]==-1)
        {
            fout<<" ";
            continue;
        }
        fout<<dist[i]<<" ";
    }
    return 0;
}