#include <bits/stdc++.h>
#define nmax 200003

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct ed{
    int q,qq,qqq;
};

vector< pair<int,int> > TT;
vector <ed> G;

int n,m,k=0,d[nmax],add,sum,r[nmax];

bool sortf(ed w, ed ww){
    return w.qqq<ww.qqq;
}

int findd(int w){
    int R,p;
    for(R=w;d[R]!=R;R=d[R]);
    while(w!=R){
        p=d[w];
        d[w]=R;
        w=p;
    }
    return R;
}

void merg(int w,int ww){
    if(r[w]<r[ww])
        d[w]=ww;
    else
        d[ww]=w;
    if(r[w]==r[ww])r[w]++;
}

int main()
{
    int a,b,c;
    fin>>n>>m;
    for(int i=1;i<=n;++i)d[i]=i,r[i]=1;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        G.push_back({a,b,c});
    }
    sort(G.begin(),G.end(),sortf);
    for(auto nr: G)cout<<nr.qqq<<' ';
    while(add!=n-1){
        int o=G[k].q,oo=G[k].qq;
        int aa=findd(o),aaa=findd(oo);
        if(aa!=aaa){
            merg(aa,aaa);
            sum+=G[k].qqq;
            add++;
            TT.push_back({G[k].q,G[k].qq});
        }
        k++;
    }
    fout<<sum<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;++i)fout<<TT[i].first<<' '<<TT[i].second<<'\n';
    return 0;
}