#include <fstream>
#define MAX 50001

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 c)
{
    PNOD p = new NOD;
    p->nod = b;
    p->c = c;
    p->urm = l[a];
    l[a] = p;     
}

void Dijkstra(int s);
void HeapDw(int i);
void HeapUp(int i);
void Swap(int a, int b);
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 Swap(int a, int b)
{
    int aux = h[a]; h[a] = h[b]; h[b] = aux;
    poz[h[a]] = a; poz[h[b]] = b;      
}

void HeapUp(int i)
{
    int k = i/2;
    if (k > 0)      
    {
        if (d[h[k]] > d[h[i]])      
        {
            Swap(k, i);
            HeapUp(k);            
        }
    }
}

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

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

void Dijkstra(int s)
{
    int i, aux, cost;
    
    for (i = 1; i <= n; i++) 
    {
        d[i] = 99999999;
        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]);         
             }
        }
    }
}