#include<cstdio>
#include<utility>
#include<vector>
#include<set>

#define N_MAX 200010
#define pb push_back
#define mp make_pair
#define INF 200010
using namespace std;

vector < pair<int,int> > G[N_MAX];
vector < pair<int,int> > Sol;
multiset < pair<int,int> > H;

int T[N_MAX],D[N_MAX],N,Cost_Final;
bool use[N_MAX];

inline void Write_Data()
{
    vector < pair<int,int> > :: iterator it;
    printf("%d\n%d\n",Cost_Final,Sol.size());
    for (it=Sol.begin();it!=Sol.end();++it)
        printf("%d %d\n",(*it).first,(*it).second);
}

inline void APM()
{
    int val,nod;
    pair <int,int> x;
    vector < pair<int,int> > ::iterator it;
    while (!H.empty())
    {
        x=*(H.begin());
        val=x.first;
        nod=x.second;
        H.erase(H.begin());
        if (T[nod]!=0) Sol.pb(mp(T[nod],nod));
        use[nod]=true;
        Cost_Final+=val;
        for (it=G[nod].begin();it!=G[nod].end();++it)
        {
            x=*it;
            if (x.second<D[x.first] && !use[x.first])
                {
                    if (D[x.first]!=INF) H.erase(H.find(mp(D[x.first],x.first)));
                    D[x.first]=x.second;
                    H.insert(mp(x.second,x.first));
                    T[x.first]=nod;
                }
        }
    }
}

inline void Load_Data()
{
    int M,i,x,y,c;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].pb(mp(y,c));
        G[y].pb(mp(x,c));
    }
    for (i=1;i<=N;i++)
    {
        use[i]=false;
        D[i]=INF;
    }
    D[1]=0;
    H.insert(mp(0,1));
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Load_Data();
    APM();
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}