#include <stdio.h>
#include<set>
#include<utility>
#include<vector>
using namespace std;
#define nmax 50005
#define inf 100000000
long n, m, i, dmin[nmax], a, b, c;
set <pair <long, long> > h;
pair <long, long> x;
vector <pair <long, long> > ma[nmax];
vector <pair <long, long> >::iterator it;

void citire()
{
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&a,&b,&c);
        ma[a].push_back(make_pair(c,b));
    }
}

void rezolvare()
{
    for (i=2;i<=n;i++)
        dmin[i]=inf;
    h.insert(make_pair(0,1));
    for (i=1;i<=n-1;i++)
    {
        x=*h.begin();    h.erase(h.begin());
        for (it=ma[x.second].begin();it!=ma[x.second].end();it++)
            if (dmin[(*it).second]>dmin[x.second]+(*it).first)
            {
                dmin[(*it).second]=dmin[x.second]+(*it).first;
                h.insert(make_pair(dmin[(*it).second],(*it).second));
            }
    }
}


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    rezolvare();
    for (i=2;i<=n;i++)
        printf("%ld ",dmin[i]);
    return 0;
}