#include <fstream>
#include <vector>
#define N_MAX 150005
#define father(x) x>>2
#define son_left(x) x<<2
#define son_right(x) (x<<2) + 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)
{
    while(VAL[NOD[poz]]<VAL[NOD[father(poz)]] && poz!=1)
    {
        schimba(poz,father(poz));
    }
}
void HEAP_DOWN(int poz)
{
    int son=1;
    while(son)
    {
        son=0;
        if(VAL[NOD[poz]]>VAL[NOD[son_left(poz)]] && son_left(poz)<=k)
        {
            son=son_left(poz);
        }
        if(VAL[NOD[son_right(poz)]]<VAL[NOD[son]] && son_right(poz)<=k)
        {
            son=son_right(poz);
        }
        if(son)
        {
            schimba(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;
}