#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
#define nmax 50005
#define inf -1
struct element{int n, c;};
int i, n, m, a, d, x;
int dmin[nmax];
vector <element> ma[nmax];
vector <element> ::iterator it;
element el;
set < pair<int, int> > h;
pair<int, int> pr;

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

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

void afisare()
{
    for (i=2;i<=n;i++)
        if (dmin[i]==inf)
            printf("0 ");
        else
            printf("%ld ",dmin[i]);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}