#include <fstream>
#include <vector>
#include <queue>
#include <cassert>
#define NMax 50001

using namespace std;

ofstream fout("dijkstra.out");

class PriorityQueue
{
private:
    pair<int, int> *arr;
    int capacity;
    int size;

    void bubble_up(int position)
    {
        int pos = position;
        pair<int, int> elem = arr[position];
        int parent = (position - 1) >> 1;

        while (pos > 0 && elem.second < arr[parent].second)
        {
            //move parent down
            arr[pos] = arr[parent];
            pos = parent;
            parent = (pos - 1) >> 1;
        }
        arr[pos] = elem;
    }

    void bubble_down(int position)
    {
        int pos = position;
        pair<int, int> elem = arr[position];

        while (pos < size)
        {
            int max_child_pos = -1;

            //it has a left child, assume it's the maximum
            if ((pos * 2 + 1) < size)
                max_child_pos = (pos * 2 + 1);

            //it has a right child, test if it's greater
            if ((pos * 2 + 2) < size && arr[2 * pos + 2].second < arr[max_child_pos].second)
                max_child_pos = (pos * 2 + 2);

            if (max_child_pos != -1 && arr[max_child_pos].second < elem.second)
            {
                pair<int, int> aux = arr[pos];
                arr[pos] = arr[max_child_pos];
                pos = max_child_pos;

                arr[pos] = aux;
            }
            else
                break;
        }
    }


public:
    PriorityQueue(int _capacity)
    {
        capacity = _capacity;
        size = 0;
        arr = new pair<int, int>[capacity];
    }

    void push(pair<int, int> p)
    {
        arr[size++] = p;
        bubble_up(size - 1);
    }

    pair<int, int> top() const
    {
        return arr[0];
    }

    void pop()
    {
        arr[0] = arr[size - 1];
        size--;
        bubble_down(0);
    }

    void set_priority(pair<int, int> p)
    {
        for (int i = 0; i < size; ++i)
            if (arr[i].first == p.first)
            {
                arr[i].second = p.second;
                bubble_up(i);
                break;
            }
    }

    int nr_elem() const
    {
        return size;
    }

    bool is_empty() const
    {
        return size == 0;
    }

};

const int inf = 1 << 30;
int n, m, final_distance[NMax];
vector< pair<int, int> > adj_list[NMax]; // adj_list[node][i] = <other_node, cost>
PriorityQueue *pq;
bool visited[NMax];

void read_data()
{
    ifstream fin("dijkstra.in");
    fin >> n >> m;
    pq = new PriorityQueue(n);
    int x, y, cost;

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> cost;
        adj_list[x].push_back(make_pair(y, cost));
    }
}

void initialize()
{
    // Inserting the source into the priority queue
    pq->push(make_pair(1, 0));
    final_distance[1] = 0;

    // Inserting the other nodes into the pq, initialized with infinity
    for (int i = 2 ; i <= n; ++i)
    {
        final_distance[i] = inf;
        pq->push(make_pair(i, inf));
    }
}

void Dijsktra()
{
    while (!pq->is_empty())
    {
        // Get the node with the smallest value associated to it
        pair<int, int> current_node = pq->top();
        pq->pop();

        for (auto it = adj_list[current_node.first].begin(); it != adj_list[current_node.first].end(); it++)
        {
            int alt_dist = current_node.second + (*it).second;
            if (alt_dist < final_distance[(*it).first])
            {
                final_distance[(*it).first] = alt_dist;
                pq->set_priority(make_pair((*it).first, alt_dist));
            }
        }
    }
}

void write_data()
{
    for (int i = 2; i <= n; ++i)
        fout << final_distance[i] << " ";
}

int main()
{
    read_data();
    initialize();
    Dijsktra();
    write_data();
    return 0;
}