#include "iostream"
#include "algorithm"
using namespace std;
structline
{
    int begin;
    int end;
    int length;
};
line Num[15001];
line Store[15001];
int father[1001], map[1001][1001], i, j, numofline, numofnode, counter;
int find(int k)
{
    return father[k]==k?k:father[k]=find(father[k]);
}
int cmp(line a, line b)
{
    return a.length<b.length;
}
void kruskal()
{
    counter = 0;
    int a, b, c, d, l;
    for(i=0; i<numofline; i++)
    {
                c = Num[i].begin;  //記錄改變前的begin結(jié)點(diǎn)
        d = Num[i].end;  //記錄改變前的edc結(jié)點(diǎn)
        l = Num[i].length;  //記錄改變前的length結(jié)點(diǎn)
        a = find(Num[i].begin);  
        b = find(Num[i].end);
        if(a!=b)
        {
            Store[counter].length = l;  //存儲(chǔ)length
            Store[counter].begin = c;  //存儲(chǔ)begin
            Store[counter++].end = d;  //存儲(chǔ)end
            father[a] = b;
        }

                //然而，我發(fā)現(xiàn)沒(méi)有必要去記錄改變前的begin,end,length等的值，

                //因?yàn)?，它們從?lái)都沒(méi)有改變過(guò)，改變的只是對(duì)應(yīng)的father中的值。

                //對(duì)于，這個(gè)的糾正就是說(shuō)明我更加理解了并查集了。
    }
}
void Init()
{
    cin>>numofnode>>numofline;
    for(i=1; i<=numofnode; i++)
        father[i] = i;
    for(i=0; i<numofline; i++)
        cin>>Num[i].begin>>Num[i].end>>Num[i].length;
    sort(Num, Num+numofline, cmp);
}
int main()
{
    Init();
    kruskal();
    cout<<Store[counter-1].length<<endl;
    cout<<counter<<endl;
    for(i=0; i<counter; i++)
        cout<<Store[i].begin<<" "<<Store[i].end<<endl;
}