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

using namespace std;

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

#define inf 10500
#define nmax 10500

vector< pair<int, int> > graph[nmax];
int n, m, tata[nmax], costuri[nmax], l, heap[2 * nmax + 100], poz[nmax];

void read() {
    f >> n >> m;
    for( int i = 0; i < m; i++) {
        int x, y, z;
        f >> x >> y >> z;
        graph[x].push_back( make_pair(y, z) );
    }
}

void introducere_in_apm(int nod) {
    for( int i = 0; i < graph[nod].size(); i++ ) {
        if( costuri[ graph[nod][i].first ] < graph[nod][i].second ) {
            costuri[ graph[nod][i].first ] = graph[nod][i].second;
            tata[graph[nod][i].first] = nod;
        }
    }
}


void prim() {
    int i;
    int viz[nmax];
    for( i = 1; i <= n; i++)
        tata[i] = 0, costuri[i] = inf, viz[i] = 0;
    
    costuri[1] = 0;
    
    priority_queue < pair< int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
    pq.push( make_pair( 0, 1 ) );

    costuri[1] = 0;
    while( !pq.empty() ) {
        int nod = pq.top().second;
        int cos = pq.top().first;cout << nod << " " << cos << "\n";
        pq.pop();
        viz[nod] = 1;
        for( auto j : graph[nod] ) {
            int cost2 = j.second;
            int nod2 = j.first;
            if( !viz[nod2] and cost2 < costuri[nod2] ) {
                costuri[nod2] = cost2;
                tata[nod2] = nod;
                pq.push( make_pair( cost2, nod2 ) );
            }
        }

    }

    for( i = 2; i <= n; i++) 
        g << i << " " << tata[i] << "\n";
} 

void functie()
{ int V = n, INF = 1000000;

    priority_queue < pair< int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq; 
  
    int src = 0; 
  
    // Create a vector for keys and initialize all 
    // keys as infinite (INF) 
    vector<int> key(V, INF); 
  
    // To store parent array which in turn store MST 
    vector<int> parent(V, -1); 
  
    // To keep track of vertices included in MST 
    vector<bool> inMST(V, false); 
  
    // Insert source itself in priority queue and initialize 
    // its key as 0. 
    pq.push(make_pair(0, src)); 
    key[src] = 0; 
  
    /* Looping till priority queue becomes empty */
    while (!pq.empty()) 
    { 
        // The first vertex in pair is the minimum key 
        // vertex, extract it from priority queue. 
        // vertex label is stored in second of pair (it 
        // has to be done this way to keep the vertices 
        // sorted key (key must be first item 
        // in pair) 
        int u = pq.top().second; 
        pq.pop(); 
  
        inMST[u] = true;  // Include vertex in MST 
  
        // 'i' is used to get all adjacent vertices of a vertex 
        for( auto i:graph[u] )
        { 
            // Get vertex label and weight of current adjacent 
            // of u. 
            int v = (i).first; 
            int weight = (i).second; 
  
            //  If v is not in MST and weight of (u,v) is smaller 
            // than current key of v 
            if (inMST[v] == false && key[v] > weight) 
            { 
                // Updating key of v 
                key[v] = weight; 
                pq.push(make_pair(key[v], v)); 
                parent[v] = u; 
            } 
        } 
    } 
  
    // Print edges of MST using parent array 
    for (int i = 1; i < V; ++i) 
        g << parent[i] << " " << i << "\n";
} 

int main() {
    read();
    functie();
    //prim();
    return 0;
}