#include <fstream>
#define MAX 50001
#define INF 0xfffffff

using namespace std;

typedef struct Nodul{
    int nod, c;
    Nodul * urm;
} NOD, *PNOD;

PNOD l[MAX];
int m, n, nh;
long long d[MAX];
int h[MAX], poz[MAX];

void Add(int a, int b, int cost)
{
    PNOD p = new NOD;
    p->nod = b;
    p->c = cost;
    p->urm = l[a];
    l[a] = p;     
}

void Dijkstra(int s);
void HeapDw(int k);
void HeapUp(int k, int l);
void Swap(int i, int j);
int ExtractMin();

int main()
{
    int i, x1, x2, cost;
    ifstream fin("dijkstra.in");
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x1 >> x2 >> cost;
        Add(x1, x2, cost);    
    }
    fin.close();
    
    Dijkstra(1);
    
    ofstream fout("dijkstra.out");
    for (i = 2; i <= n; i++)    
        fout << d[i] << " ";
    fout.close();
    
    return 0;
}

void HeapUp(int k)
{
    if (k == 1) return;
    int tata = k/2;
    if (d[h[k]] < d[h[tata]])    
    {
        Swap(k, tata);
        HeapUp(tata);    
    }
}

void HeapDw(int k, int l)
{
    if (2*k <= l)
    {
        int i = 2*k;
        if (i+1 <= l && d[h[i]] > d[h[i+1]]) i++;
        if (d[h[k]] > d[h[i]])    
        {
            Swap(k, i);
            HeapDw(i, l);        
        }
    }
}

void Swap(int i, int j)
{
    int aux = h[i]; h[i] = h[j]; h[j] = aux;
    poz[h[i]] = i; poz[h[j]] = j;    
}

int ExtractMin()
{
    int min = h[1];
    Swap(1, nh);
    poz[h[nh]] = 0;
    nh--;
    HeapDw(1, nh);
    
    return min;    
}

void Dijkstra(int s)
{
    int i, aux, cost;
    
    for (i = 1; i <= n; i++) 
    {
        d[i] = INF;
        poz[i] = h[i] = i;    
    }
        
    d[s] = 0; nh = n;
    for (i = 1; i <= n; i++)        
        HeapUp(i);
    
    while (nh)
    {
        aux = ExtractMin();
        for (PNOD p = l[aux]; p; p = p->urm)        
        {
             i = p->nod;
             cost = p->c;
             if (d[i] > d[aux] + cost)   
             {
                 d[i] = d[aux] + cost;
                 HeapUp(poz[i]);         
             }
        }
    }
}