#include <fstream>
#include <vector>

using namespace std;
ifstream fin  ("dijkstra.in");
ofstream fout ("dijkstra.out");

const long int NMAX = 50005;
const int INFINIT = 1 << 30;

struct edge {
    int x, y, z;
};

int N, M, poz[NMAX];
vector < vector < edge > > lista(NMAX);
vector < int > dist(NMAX, INFINIT);

struct Heap {
    int arr[NMAX], c;
    
    Heap()
    {
        c = 0;
        for(int i = 1; i < NMAX; i++)
            arr[i] = 0;
    }
    
    void heapify_up(int index)
    {
        int cp = index;
        bool heap = false;
        while(cp > 1 && !heap)
        {
            if(dist[arr[cp]] >= dist[arr[cp / 2]])
                heap = true;
            else
            {
                int aux = arr[cp];
                arr[cp] = arr[cp / 2];
                arr[cp / 2] = aux;
                aux = poz[arr[cp]];
                poz[arr[cp]] = poz[arr[cp / 2]];
                poz[arr[cp / 2]] = aux;
                cp /= 2;
            }
        }
    }
    
    void heapify_down(int index)
    {
        int cp = index;
        bool heap = false;
        while(cp < c && !heap)
        {
            if(dist[arr[cp]] <= dist[arr[cp * 2]] && dist[arr[cp]] <= dist[arr[cp * 2 + 1]])
                heap = true;
            else
                if(dist[arr[cp]] > dist[arr[cp * 2]] && dist[arr[cp * 2]] < dist[arr[cp * 2 + 1]])
                {
                    int aux = arr[cp];
                    arr[cp] = arr[cp * 2];
                    arr[cp * 2] = aux;
                    aux = poz[arr[cp]];
                    poz[arr[cp]] = poz[arr[cp * 2]];
                    poz[arr[cp * 2]] = aux;
                    cp *= 2;
                }
                else
                {
                    int aux = arr[cp];
                    arr[cp] = arr[cp * 2 + 1];
                    arr[cp * 2 + 1] = aux;
                    aux = poz[arr[cp]];
                    poz[arr[cp]] = poz[arr[cp * 2 + 1]];
                    poz[arr[cp * 2 + 1]] = aux;
                    cp *= 2; cp++;
                }
        }
    }
    
    void push(int nod)
    {
        arr[++c] = nod;
        poz[nod] = c;
        heapify_up(c);
    }
    
    int pop()
    {
        int head = arr[1];
        poz[head] = 0;
        arr[1] = arr[c--];
        arr[c + 1] = 0;
        poz[arr[1]] = 1;
        heapify_down(1);
        return head;
    }
    
    void actualizare(int index)
    {
        heapify_up(index);
        heapify_down(index);
    }
    
    bool empty()
    {
        return c == 0;
    }
};

void dijkstra(int nod)
{
    Heap *coada = new Heap();
    dist[nod] = 0;
    for(unsigned int i = 0; i < lista[nod].size(); i++)
    {
        dist[lista[nod][i].y] = lista[nod][i].z;
        coada->push(lista[nod][i].y);
    }
    
    while(!coada->empty())
    {
        int node = coada->pop();
        
        for(unsigned int i = 0; i < lista[node].size(); i++)
        {
            if(dist[lista[node][i].y] == INFINIT)
                coada->push(lista[node][i].y);
            if(dist[lista[node][i].y] > dist[lista[node][i].x] + lista[node][i].z)
            {
                dist[lista[node][i].y] = dist[lista[node][i].x] + lista[node][i].z;
                coada->actualizare(poz[lista[node][i].y]);
            }
        }
    }
    
    for(int i = 2; i <= N; i++)
        if(dist[i] == INFINIT)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
}

int main()
{
    fin >> N >> M;
    for(int i = 0 ; i < M; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        edge e;
        e.x = x; e.y = y; e.z = z;
        lista[x].push_back(e);
    }

    dijkstra(1);
    fin.close();
    fout.close();
    return 0;
}