// MST and Dijkstra compared
// Note the sort method in Kruskal alg.
 
import java.util.*;
import java.io.*;
 
public class Solvers {
 
static void dijkstraNsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];
 
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }
 
    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}
 
public static void dijkstraElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];
 
  PriorityQueue <Integer> pq
    = new PriorityQueue<Integer> (g.N,
          new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );
 
  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for(int i = 0; i < g.N; i++) {
    // take the closest node
    while( closed[currnode = pq.poll()] == true );
    // and expand it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}
 
 
static void MST_Nsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];
 
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }
 
    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}
 
 
 
public static void MST_ElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];
 
  PriorityQueue <Integer> pq
    = new PriorityQueue<Integer> (g.N,
          new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );
 
  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for(int i = 0; i < g.N; i++) {
    // take the closest node
    while( closed[currnode = pq.poll()] == true );
    // and expand it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}
 
 
public static void MST_Kruskal(Graph g, int [] edgesMST ) {
 
  // store edges in one arr and sort them
  int [] edges = new int[g.M*3];
  int k = 0;
  for( int i = 0; i < g.N; i++ )
    for( int j = 0; j < g.dg[i]; j++ ) {
      if( i <  g.edge[i][j] ) {
        edges[k++] = g.w[i][j];
        edges[k++] = i;
        edges[k++] = g.edge[i][j];
      }
    }
   qSort3( edges, 0, edges.length-3 );
 
   // construct the MST with UF
   initUF( g.N );
   int edgesCount = 0, set1, set2;
   k = 0;
   while( edgesCount < g.N-1 ){
     set1 = UF_find(edges[k+1]); set2 = UF_find(edges[k+2]);
     if( set1 != set2 ) {  // found an edge of MST
       UF_union( set1, set2 );
       edgesCount++;
       edgesMST[edgesCount*2-2] = edges[k+1]; edgesMST[edgesCount*2-1] = edges[k+1] ;
     }
     k += 3;
   }
}
 
 
 
  public static void main( String[] args ) {
  int [] p = {3, 10, 11, -3, 22, 25, 7, 33, 34, 4, 42, 43, 2, 56, 56 };
  qSort3(p, 0, p.length-3);
  list(p);
 
 
  }
 
 
static void list (int [] a) {
  for( int x : a )
    System.out.printf("%2d ", x);
  System.out.printf("\n");
}
 
 
 
static void qSort(double a[], int low, int high) {
  int iL = low, iR = high;
  double pivot = a[low];
  double aux;
  do {
    while (a[iL] < pivot) iL++;
    while (a[iR] > pivot) iR--;
    if (iL < iR) {
      //swap(a,iL, iR);
      aux = a[iL]; a[iL] = a[iR]; a[iR] = aux;
       iL++; iR--;
    }
    else
      if (iL == iR) { iL++; iR--;}
 
  } while( iL <= iR);
 
  if (low < iR)  qSort(a, low, iR);
  if (iL < high) qSort(a, iL, high);
}
 
 
// always points to i%3=0 elem which stores the key
static void qSort3(int a[], int low, int high) {
  int iL = low, iR = high;
  int pivot = a[low];
  int aux;
  do {
    while (a[iL] < pivot) iL+=3;
    while (a[iR] > pivot) iR-=3;
    if (iL < iR) {
      //swap(a,iL, iR);
      for(int k = 0; k < 3; k++ )
      { aux = a[iL+k]; a[iL+k] = a[iR+k]; a[iR+k] = aux; }
      iL+=3; iR-=3;
    }
    else
      if (iL == iR) { iL+=3; iR-=3;}
 
  } while( iL <= iR);
 
  if (low < iR)  qSort3(a, low, iR);
  if (iL < high) qSort3(a, iL, high);
}
 
// uf
 
static int [] sets;
static int [] sizes;
static int elem1;
 
 
static void initUF(int n) {
  sets = new int [n];
  sizes = new int [n];
  for(int i = 0; i < n; i++) {
    sets[i] = i;
    sizes[i] = 1;
  }
}
 
static void UF_union(int a, int b) {
  //System.out.printf(" unioning %d %d \n", a, b);
  if (sizes[b] > sizes[a]) {
    sets[a] = b;
    sizes[b] += sizes[a];
  }
  else {
    sets[b] = a;
    sizes[a] += sizes[b];
  }
}
 
static int UF_find(int a) {
  elem1 = a;
  while (a != sets[a])
    a = sets[a];
  sets[elem1] = a;  // shorten the path
  return a;
}
 
static void listSet(int a) {  // for debuggin purposes only
  int finda = UF_find(a);
  for(int i = 0; i < sets.length; i++)
    if(UF_find(i) == finda)
      System.out.printf("%d ", i);
  System.out.printf("\n");
}
 
}

//Petr Poliak o Longslopes:
 
include <bits/stdc++.h>
#define FOR(A, B) for(int (A) = 0; (A) < (B); (A)++)
#define pb push_back
#define mp make_pair
 
using namespace std;
 
pair<int,int> edges[5555*5554/2];
int meaningful[5555];
int wedges[5555][5555];
vector< vector<int> > paths;
 
int main() {
	int n,m;
	scanf("%d %d", &n, &m);
	FOR(i, m) {
		int a,b,c;
		scanf("%d %d %d", &a, &b, &c);
		if(meaningful[a] < b) meaningful[a] = b;
		edges[i].first = a;
		edges[i].second = b;
		wedges[a][b] = c;
		wedges[b][a] = c;
	}
	vector< pair<int, int> > besties;
	sort(edges, edges+m);
	FOR(i, n) paths.pb(vector<int>());
	int maxx = 0, aclen;
	FOR(i, m) {
		paths[edges[i].second].pb(edges[i].first);
		if (wedges[edges[i].first][edges[i].second] >= maxx) {
			if (wedges[edges[i].first][edges[i].second] > maxx) {
				maxx = wedges[edges[i].first][edges[i].second];
				besties.clear();
			}
			besties.pb(mp(edges[i].first, edges[i].second));
		}
		for(int j = 0; j < paths[edges[i].first].size(); j++) {
			int t = paths[edges[i].first][j];
			if (edges[i].second > meaningful[t]) continue;
			aclen = wedges[edges[i].first][edges[i].second] + wedges[edges[i].first][t];
			if (aclen > wedges[edges[i].second][t]) {
				if (wedges[edges[i].second][t] == 0) paths[edges[i].second].pb(t);
				wedges[edges[i].second][t] = aclen;
				if (wedges[t][edges[i].second] > 0) {
					if (aclen >= maxx) {
						if (aclen > maxx) {
							besties.clear();
							maxx = aclen;
						}
						besties.pb(mp(t, edges[i].second));
					}
				}
			}
		}
	}
	sort(besties.begin(), besties.end());
	printf("%d %d\n", besties[0].first, besties[0].second);
	for(int i = 1; i < besties.size(); i++) {
		if(besties[i] != besties[i-1])
			printf("%d %d\n", besties[i].first, besties[i].second);
	}
	return 0;
}