#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

long long n,m,i,j,s,nr,rs,a,b,poz[100001];
long long dr[100001];
struct ab
{
    long long c;
    int nod;
};
bool anal[100001];
vector<ab>t[100001];
ab h[100001],x;

void sus(int nod)
{
    if (nod>1 && h[nod].c<h[nod>>1].c)
    {
        swap(poz[h[nod].nod],poz[h[nod>>1].nod]);
        swap(h[nod],h[nod>>1]);
        sus(nod>>1);
    }
}

void jos(int nod)
{
    int son=nod*2;
    if (son<=nr)
        if (son+1<=nr && h[son+1].c<h[son].c && h[son+1].c<h[nod].c)
        {
            swap(poz[h[nod].nod],poz[h[son+1].nod]);
            swap(h[nod],h[son+1]);
            jos(son+1);
        }
        else
        if (h[son].c<h[nod].c)
        {
            swap(poz[h[nod].nod],poz[h[son].nod]);
            swap(h[nod],h[son]);
            jos(son);
        }
    return;
}

void scot(int nod)
{
      swap(poz[h[nod].nod],poz[h[nr].nod]);
      h[nod]=h[nr];
      nr--;
      jos(nod);
}

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b>>s;
        x.nod=b;
        x.c=s;
        t[a].push_back(x);
    }
    nr=0;
    for (i=0;i<t[1].size();i++)
    {
        nr++;
        h[nr]=t[1][i];
        anal[t[1][i].nod]=1;
        poz[t[1][i].nod]=nr;
        dr[t[1][i].nod]=t[1][i].c;
        sus(nr);
    }
    anal[1]=1;
    while (nr)
    {
        x=h[1];
        scot(1);
        for (int i=0;i<t[x.nod].size();i++)
            if (anal[t[x.nod][i].nod]==0)
            {
                 anal[t[x.nod][i].nod]=1;
                 nr++;
                 h[nr]=t[x.nod][i];
                 h[nr].c+=x.c;
                 dr[h[nr].nod]=h[nr].c;
                 poz[h[nr].nod]=nr;
                 sus(nr);
            }
            else
            if (t[x.nod][i].c+x.c<dr[t[x.nod][i].nod])
            {
                scot(poz[t[x.nod][i].nod]);
                nr++;
                h[nr]=t[x.nod][i];
                h[nr].c+=x.c;
                dr[h[nr].nod]=h[nr].c;
                poz[h[nr].nod]=nr;
                sus(nr);
            }
    }
    for (i=2;i<=n;i++)
        fout<<dr[i]<<" ";
    return 0;
}