#include <fstream>
#include <vector>
#define N_MAX 150005
#define father(x) x>>1
#define son_left(x) x<<1
#define son_right(x) (x<<1) + 1
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int NOD[N_MAX],P[N_MAX],VAL[N_MAX],n,m,k;
struct pereche{
    int x;
    int y;
};
vector < pereche > lista[N_MAX];
void schimba(int &a, int b)
{
    swap(P[a],P[b]);
    swap(NOD[P[a]],NOD[P[b]]);
    a=b;
}
void HEAP_UP(int poz)
{
    int f;
    while(poz>1)
    {
        f=father(poz);
        if(VAL[NOD[f]]>VAL[NOD[poz]])
        {
            P[NOD[f]]=poz;
            P[NOD[poz]]=f;
            swap(NOD[poz],NOD[f]);
            poz=f;
        }
        else
            poz=1;
    }
}
void HEAP_DOWN(int poz)
{
    int son;
    while(poz<=k)
    {
        son=poz;
        if(son_left(son)<=k)
        {
            son=son_left(son);
            if(son+1<=k)
            {
                if(VAL[NOD[son+1]]<VAL[NOD[son]])
                {
                    son++;
                }
            }
        }
        else
            return;
        if(VAL[NOD[poz]]>VAL[NOD[son]])
        {
            P[NOD[son]]=poz;
            P[NOD[poz]]=son;
            swap(NOD[son],NOD[poz]);
            poz=son;
        }
    }
}
void cut()
{
    P[NOD[k]]=P[NOD[1]];
    NOD[1]=NOD[k];
    k--;
    HEAP_DOWN(1);
}
void ADD(int x)
{
    k++;
    NOD[k]=x;
    HEAP_UP(k);
}
void Dijkstra()
{
    for(int i=2; i<=n; i++)
    {
        P[i]=-1;
    }
    NOD[1]=1;
    P[1]=1;
    k++;
    while(k)
    {
        int mi=NOD[1];
        cut();
        for(int i=0; i<lista[mi].size(); i++)
        {
            if(VAL[mi]+lista[mi][i].y<VAL[lista[mi][i].x] || !VAL[lista[mi][i].x])
            {
                VAL[lista[mi][i].x]=VAL[mi]+lista[mi][i].y;
                if(P[lista[mi][i].x]==-1)
                {
                    ADD(lista[mi][i].x);
                }
                else
                {
                    HEAP_UP(P[lista[mi][i].x]);
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int x;
        pereche o;
        cin >> x >> o.x >> o.y;
        lista[x].push_back(o);
    }
    Dijkstra();
    for(int i=2; i<=n; i++)
    {
        cout << VAL[i] << ' ';
    }
    return 0;
}