#include <fstream>
#include <vector>
#define N_MAX 50005
#define father(x) x>>1
#define son_left(x) x<<1
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m,k,NOD[N_MAX],P[N_MAX],VAL[N_MAX];
struct pereche{
    int x;
    int y;
};
vector <pereche> lista[N_MAX];
void DOWN_HEAP(int poz)
{
    int son=1;
    while(son)
    {
        son=0;
        if(son_left(poz)<=k)
        {
            son=son_left(poz);
            if(son+1<=k && VAL[NOD[son]]>VAL[NOD[son+1]])
            {
                son++;
            }
            if(VAL[NOD[son]]>=VAL[NOD[poz]])
            {
                son=0;
            }
        }
        if(son)
        {
            P[NOD[poz]]=son;
            P[NOD[son]]=poz;
            swap(NOD[son],NOD[poz]);
            poz=son;
        }
    }
}
void UP_HEAP(int poz)
{
    int o=NOD[poz];
    while(k>1 && o<VAL[father(poz)])
    {
        P[NOD[father(poz)]]=poz;
        NOD[poz]=NOD[father(poz)];
        poz=father(poz);
    }
    NOD[poz]=o;
    P[o]=poz;
}
void DIJKSTRA()
{
    for(int i=2; i<=n; i++)
    {
        P[i]=-1;
    }
    P[1]=1;
    NOD[1]=1;
    k++;
    while(k)
    {
        int mi=NOD[1];
        P[NOD[k]]=1;
        swap(NOD[1],NOD[k]);
        k--;
        DOWN_HEAP(1);
        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)
                {
                    k++;
                    P[lista[mi][i].x]=k;
                    NOD[k]=lista[mi][i].x;
                    UP_HEAP(P[lista[mi][i].x]);
                }
                else
                {
                    UP_HEAP(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;
}