#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <sstream>
using namespace std;
typedef long long LL;
const LL INF = 0x5fffffff;
const double EXP = 1E-6;
const LL MOD = (LL)1E9+7;
const int MS = 1005;

struct edge {
    int u, v, w;
    bool operator < (const edge & a) const {
        return w < a.w;
    }
}edges[15005];

int fa[MS];
int ans[MS];
int n, m;

int find(int x) {
    int s = x;
    while (fa[s] >= 0)
        s = fa[s];
    while (s != x) {
        int t = fa[x];
        fa[x] = s;
        x = t;
    }
    return s;
}

void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    int t = fa[fx] + fa[fy];
    if (fa[fx] > fa[fy]) {
        fa[fx] = fy;
        fa[fy] = t;
    }
    else {
        fa[fy] = fx;
        fa[fx] = t;
    }
}

void MST() {
    memset(fa,-1,sizeof(fa));
    sort(edges, edges + m);
    int c = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(u) != find(v)) {
            ans[c++] = i;
            merge(u,v);
        }
        if (c >= n -1)
            break;
    }
    printf("%d\n",edges[ans[c - 1]].w);
    printf("%d\n",n - 1);
    for (int i = 0; i < c; i++) {
        printf("%d %d\n", edges[ans[i]].u, edges[ans[i]].v);
    }
}


int main() {
    while (scanf("%d %d",&n,&m) != EOF) {
        int u, v, w;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
        }
        MST();
    }
    return 0;
}