#include <vector>
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>

#define nmax 50001


using namespace std;

vector < pair <int, int> > v[ nmax ];
priority_queue <pair <int, int>, vector < pair<int, int> >, greater< pair<int, int> > > q;
int dist[ nmax ];

void solve(int n);

int main() {
    ifstream cin("dijkstra.in");
    ///ofstream cout("dijkstra.out");

    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n; ++i)
        dist[ i ] = INT_MAX;

    for (int i = 0, x, y, z; i < m; ++i) {
        cin >> x >> y >> z;
        v[ x ].push_back({y, z});
    }

    solve(n);

}

void solve(int n) {
    q.push({0, 1});

    while (q.empty() == false) {
        int nod = q.top().first;
        int cost = q.top().second;
        q.pop();

        cout << nod << " " << cost;
    }

}