Cod sursa(job #825150)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mkp make_pair
using namespace std;
const int maxn = 200200;
const int INF = 200000200;
int VEC[maxn],ANS,V[maxn],H[maxn * 2 + 100],POZ[maxn];
vector <pair<int,int> > G[maxn],VANS;
int N,M,L,C[maxn];
void push(int poz)
{
while((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
{
if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
{
swap(H[poz],H[poz * 2]);
swap(POZ[H[poz]],POZ[H[poz * 2]]);
poz *= 2;
}
else
{
swap(H[poz],H[poz * 2 + 1]);
swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
poz = poz * 2 + 1;
}
}
}
void pop(int poz)
{
while(poz > 1 && V[H[poz]] < V[H[poz / 2]])
{
swap(H[poz],H[poz / 2]);
swap(POZ[H[poz]],POZ[H[poz / 2]]);
poz = poz / 2;
}
}
void Insert(int nod)
{
H[++L] = nod;
POZ[nod] = L;
pop(L);
}
int Minim()
{
int x = H[1];
swap(H[1],H[L]);
swap(POZ[H[1]],POZ[H[L]]);
L--;
push(1);
POZ[x] = 0;
return x;
}
void Select(int x)
{
for(unsigned int i = 0;i < G[x].size(); ++i)
{
int nod = G[x][i].first;
int cost = G[x][i].second;
V[nod] = min(V[nod],cost);
if (V[nod] == cost) VEC[nod] = x;
if (POZ[nod]) pop(POZ[nod]);
}
}
void Read()
{
int i,x,y,c;
freopen("apm.in","r",stdin);
scanf("%d %d\n",&N,&M);
for(i = 1;i <= M; ++i)
{
scanf("%d %d %d",&x,&y,&c);
G[x].pb(mkp(y,c));
G[y].pb(mkp(x,c));
}
}
void Print()
{
freopen("apm.out","w",stdout);
printf("%d\n%d\n",ANS,N-1);
for(int i = 1;i <= N; ++i)
printf("%d %d\n",i,VEC[i]);
}
int main()
{
Read();
for(int i = 2;i <= N; ++i)
V[i] = INF;
Select(1);
for(int i = 2;i <= N; ++i)
{
Insert(i);
}
for(int i = 1;i < N; ++i)
{
int x = Minim();
Select(x);
ANS += V[x];
}
Print();
return 0;
}