#include<bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int nmax = 100001;

struct muchie_prop{
    int cost;
};
struct pairCompSec {
    constexpr bool operator()(pair<int, int> const& a,pair<int, int> const& b) const noexcept{
        return a.second > b.second;
    }
};

class Graf{
    int n, m;
    vector<pair<int, muchie_prop>>vecin[nmax];


    void recursieDFS(int nod, bool vizitat[]){
        vizitat[nod]=true;
        for(int i=0; i<vecin[nod].size(); ++i)
            if(vizitat[vecin[nod][i].first]==false)
                recursieDFS(vecin[nod][i].first, vizitat);

    }
    void recursieDFSdistante(int nod, int vizitat[],int k){
        vizitat[nod]=k;
        for(int i=0; i<vecin[nod].size(); ++i)
            if(vizitat[vecin[nod][i].first]==-1)
                recursieDFSdistante(vecin[nod][i].first, vizitat,k+1);

    }

    void recursieDFS_sort(int nod, bool vizitat[],stack <int> &s){
        vizitat[nod]=true;
        for(int i=0; i<vecin[nod].size(); ++i)
            if(vizitat[vecin[nod][i].first]==false)
                recursieDFS_sort(vecin[nod][i].first, vizitat,s);

        s.push(nod);

    }



    void recursieCTC(int nod, int vizitat[], int varf[], stack <int> &s, bool scheck[], int &cont,int &nr,int sol[],int &k){

        vizitat[nod]=cont;
        scheck[nod]=true;
        varf[nod]=cont;
        s.push(nod);
        for(int i=0; i<vecin[nod].size(); ++i){
            if(vizitat[vecin[nod][i].first]==-1){
                cont=cont+1;
                recursieCTC(vecin[nod][i].first, vizitat,varf,s,scheck,cont,nr,sol,k);
                varf[nod]=min( varf[nod], varf[ vecin[nod][i].first ] );
            }else if(scheck[vecin[nod][i].first]==true) varf[nod]=min( varf[nod], vizitat[ vecin[nod][i].first ] );
        }
        if( varf[nod] == vizitat[nod] ){
            nr++;
            while(s.top()!=nod){
                sol[k]=s.top(); k++;
                scheck[s.top()]=false;
                s.pop();
            }
            sol[k]=s.top(); k++;
            sol[k]=-1; k++;
            scheck[s.top()]=false;
            s.pop();
        }

    }

    void recursieBC(int nod, int vizitat[], int varf[], stack <int> &s, int &cont, int &nr,int sol[],int &k){

        vizitat[nod]=cont;
        varf[nod]=cont;
        cont++;
        s.push(nod);
        for(int i=0; i<vecin[nod].size(); ++i){
            if(vizitat[vecin[nod][i].first]==-1){

                s.push(nod*(-1));
                recursieBC(vecin[nod][i].first, vizitat,varf,s,cont,nr,sol,k);

                if( varf[ vecin[nod][i].first ] >= vizitat[nod] ){
                    nr++;
                    while(s.top()!=nod && s.top()!=nod*(-1)){
                        if(s.top()>0){ sol[k]=s.top(); k++;}
                        s.pop();
                    }
                    sol[k]=nod; k++;
                    sol[k]=-1; k++;
                }else{
                    varf[nod]=min( varf[nod], varf[ vecin[nod][i].first ] );
                }

            }else varf[nod]=min( varf[nod], vizitat[ vecin[nod][i].first ] );
        }


    }

public:

    Graf(int n, int m){
        this->n=n;
        this->m=m;
    }

    void citireM( bool orient , int nivel_costuri=0){

        for( int i=0; i<m; ++i ){

            muchie_prop pr;

            int a, b, c;
            in >> a >> b;
            if( nivel_costuri>=1 ){
                in>>c;
                pr.cost=c;
            }

            vecin[a].push_back({b,pr});

            if( orient == false ){
                vecin[b].push_back({a,pr});
            }
        }
    }

    void DFS(){

        int nr_comp_conex=0;
        bool vizitat[n];

        for(int i=1;i<=n;++i)
            vizitat[i]=false;

        for(int i=1;i<=n;++i){
            if(vizitat[i]==false){
                recursieDFS(i,vizitat);
                nr_comp_conex++;
            }
        }
        out<<nr_comp_conex;

    }

    void BFS(int s){

        int drum[n+1];

        for(int i=1;i<=n;++i)
            drum[i]=-1;

        drum[s]=0;
        queue <int> poz;
        poz.push(s);

        while(!poz.empty()){
            int nod=poz.front();
            for(int i=0; i<vecin[nod].size(); ++i){
                if( drum[vecin[nod][i].first] == -1 ){
                    poz.push( vecin[nod][i].first );
                    drum[vecin[nod][i].first]=drum[nod]+1;
                }
            }
            poz.pop();
        }

        for(int i=1;i<=n;++i)
            out<<drum[i]<<" ";

    }

    void CTC(){
        int desc[n+1], varf[n+1];
        stack <int> s;
        bool scheck[n+1];
        for(int i=1;i<=n;++i){
            desc[i]=-1;
            varf[i]=-1;
            scheck[i]=false;
        }
        int cont=0,nr=0,solutie[2*n+5], k=0;
        for(int i=1;i<=n;++i){
            if(desc[i]==-1)
                recursieCTC(i,desc,varf,s,scheck,cont,nr,solutie,k);

        }
        out<<nr<<"\n";
        int j=k-2;
        while(j>=0){
            while(solutie[j]!=-1 && j>=0){
                out<<solutie[j]<<" ";
                --j;
            }
            nr--; j--; out<<"\n";
        }

    }

    void BC(){
        int desc[n+1], varf[n+1];
        stack <int> s;
        for(int i=1;i<=n;++i){
            desc[i]=-1;
            varf[i]=-1;
        }
        int cont=0,nr=0,solutie[2*n+5], k=0;
        for(int i=1;i<=n;++i){
            if(desc[i]==-1){
                if(vecin[i].empty()==true){

                    nr++;
                    solutie[k]=i; k++;
                    solutie[k]=-1; k++;
                }else{

                    recursieBC(i,desc,varf,s,cont,nr,solutie,k);
                }
                while(s.empty()!=true) s.pop();
            }

        }
        out<<nr<<"\n";
        int j=k-2;
        while(j>=0){
            while(solutie[j]!=-1 && j>=0){
                out<<solutie[j]<<" ";
                --j;
            }
            nr--; j--; out<<"\n";
        }


    }


    bool HH(){
        int grad[n+3];
        for(int i=1; i<=n;++i)
            in>>grad[i];
        sort(grad+1,grad+n+1,greater<int>());

        int nr0=0;
        for(int i=1; i<=n; ++i){
            if(grad[i]==0) return true;
            if(grad[i]>n-i) return false;
            if(grad[i]==1){
                if((n-i-nr0+1)%2==0) return true;
                else return false;
            }
            for(int j=i+1; j<=i+grad[i]; ++j){

                grad[j]--;
                if(grad[j]<0) return false;
                if(grad[j]==0) nr0++;
            }
            sort(grad+i+1,grad+n+1,greater<int>());
        }
        return true;
    }

    void ST(){
        bool vizitat[n+1];
        stack <int> st;

        for(int i=1; i<=n;++i)
            vizitat[i]=false;
        for(int i=1; i<=n;++i)
            if(vizitat[i]==false)
                recursieDFS_sort(i,vizitat,st);

        while(st.empty()!=true){
            out<<st.top()<<" ";
            st.pop();
        }
    }
    int Darb(){
        int distante[100001];
        for(int i=1;i<=n;++i)
            distante[i]=-1;
        recursieDFSdistante(1,distante,0);
        int nod_mac=1,mac=0;
        for(int i=1;i<=n;++i){
            if(distante[i]>mac)
            {
                mac=distante[i];
                nod_mac=i;
            }
            distante[i]=-1;
        }
        recursieDFSdistante(nod_mac,distante,0);
        for(int i=1;i<=n;++i)
            if(distante[i]>mac)
                mac=distante[i];

        return mac+1;



    }

    void Roy_Floyd(int M[101][101]){
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j){
                    if( (M[i][j] > M[i][k]+M[k][j] || ( M[i][j]==0 && i!=j )) && M[i][k]!=0 && M[k][j]!=0)
                        M[i][j]=M[i][k]+M[k][j];
                }
    }

    void Dijkstra(int start, int dist[]){
        bool viz[n+1];
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > dist_min;
        for( int i=1; i<=n; ++i ){
            viz[i]=false;
            dist[i]=-1;
        }
        int p = start;
        dist[start]=0;

        for( int i=1; i<=n; ++i ){
            viz[p]=true;
            for( int j=0; j< vecin[p].size(); ++j ){
                int nvec = vecin[p][j].first;
                if( !viz[nvec] && ( dist[nvec] == -1  ||  dist[nvec] > dist[p]+ vecin[p][j].second.cost ) ){
                    dist[nvec]= dist[p]+ vecin[p][j].second.cost;
                    dist_min.push( make_pair(dist[nvec], nvec) );
                }

            }

            while( viz[ dist_min.top().second ] && !dist_min.empty() )
                dist_min.pop();
            if(!dist_min.empty()){
                p=dist_min.top().second;
                dist_min.pop();
            }

        }

    }

    void APM(int &cost_m, pair<int,int> muchii_apm[]){

        bool apm[n+1];
        int parent[n+1],pcost[n+1];
        for(int i=0; i<n+1; ++i){
            apm[i]=false;
            pcost[i]=-1;
        }


        priority_queue<pair<int,int>, vector<pair<int,int>>, pairCompSec > dist_min;
        dist_min.push({1,0});

        for(int i=0; i<n; ++i){
            while(apm[dist_min.top().first]==true)
                dist_min.pop();

            int nod=dist_min.top().first;
            cost_m+=dist_min.top().second;
            dist_min.pop();
            muchii_apm[i]={parent[nod],nod};
            apm[nod]=true;
            for(int j=0; j<vecin[nod].size(); ++j){
                if( apm[vecin[nod][j].first]==false ){

                    if(pcost[vecin[nod][j].first]==-1 || vecin[nod][j].second.cost < pcost[vecin[nod][j].first]){
                        parent[vecin[nod][j].first]=nod;
                        pcost[vecin[nod][j].first]=vecin[nod][j].second.cost;
                    }

                    dist_min.push( {vecin[nod][j].first, vecin[nod][j].second.cost} );
                }

            }
        }



    }

    void BellF(int &cost_m, pair<int,int> muchii_apm[]){
        bool apm[n+1];

        int parent[n+1],pcost[n+1];
        for(int i=0; i<n+1; ++i){
            apm[i]=false;
            pcost[i]=-1;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, pairCompSec > dist_min;
        dist_min.push({1,0});

        for(int i=0; i<n; ++i){
            while(apm[dist_min.top().first]==true)
                dist_min.pop();

            int nod=dist_min.top().first;
            cost_m+=dist_min.top().second;
            dist_min.pop();
            muchii_apm[i]={parent[nod],nod};
            apm[nod]=true;
            for(int j=0; j<vecin[nod].size(); ++j){
                if( apm[vecin[nod][j].first]==false ){

                    if(pcost[vecin[nod][j].first]==-1 || vecin[nod][j].second.cost < pcost[vecin[nod][j].first]){
                        parent[vecin[nod][j].first]=nod;
                        pcost[vecin[nod][j].first]=vecin[nod][j].second.cost;
                    }

                    dist_min.push( {vecin[nod][j].first, vecin[nod][j].second.cost} );
                }

            }
        }



    }



};




int main()
{
    int n=0,m=0;
    in>>n>>m;
    Graf graf= Graf(n,m);
    graf.citireM(false,1);
    pair<int,int> muchii_apm[n];
    int cost=0;
    graf.APM(cost,muchii_apm);
    out<<cost<<'\n'<<n-1<<'\n';
    for(int i=1; i<n;++i)
        out<<muchii_apm[i].first<<' '<<muchii_apm[i].second<<'\n';

    return 0;
}