#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;
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 push(int nod)
    {
        arr[++c] = nod;
        int cp = c;
        // PROMOVARE
        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;
                cp /= 2;
            }
        }
    }
    
    int pop()
    {
        int head = arr[1];
        arr[1] = arr[c--];
        arr[c + 1] = 0;
        int cp = 1;
        // CERNERE
        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;
                    cp *= 2;
                }
                else
                {
                    int aux = arr[cp];
                    arr[cp] = arr[cp * 2 + 1];
                    arr[cp * 2 + 1] = aux;
                    cp *= 2; cp++;
                }
        }
        return head;
    }
    
    bool empty()
    {
        return c == 0;
    }
};

void dijkstra(int nod)
{
    Heap coada;
    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;
        }
    }
    
    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;
}