#include <bits/stdc++.h>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int nmax = 5e4 + 3;

struct node
{
    int cost;
    int nod;
};

int n, m, x, y, c, d[nmax];

priority_queue < pair <int, int> > q;

vector <node> v[nmax];

int main()
{
    f >> n >> m;
    for (int i = 2; i <= n; ++i)
        d[i] = 2e9;

    while (m--)
    {
        f >> x >> y >> c;
        node usu;
        usu.cost = c;
        usu.nod = y;
        v[x].push_back(usu);
        usu.nod = x;
        v[y].push_back(usu);
    }

    q.push(make_pair(0, 1));

    while (!q.empty())
    {
        int nod = q.top().second;
        q.pop();

        for (int i = 0; i < v[nod].size(); ++i)
        {
            node it = v[nod][i];
            cout << it.cost << ' ' << d[nod] << '\n';
            if (it.cost + d[nod] < d[it.nod])
            {
                d[it.nod] = it.cost + d[nod];
                q.push(make_pair(-d[it.nod], it.nod));
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        g << d[i] << ' ';
    return 0;
}