#include <stdio.h>
#include <stdlib.h>
#define infile "radiatie.in"
#define outfile "radiatie.out"
#define NMAX 15005
#define MCHMAX 30005
struct muchie{int u,v,c;};
struct NOD{int x,c; struct NOD *adr;};
FILE *fin,*fout;
int n,m,k;
muchie mch[MCHMAX];
char used[MCHMAX];
int precarb[NMAX];
NOD *prim[NMAX];
char vizitat[NMAX];
int prec[NMAX],niv[NMAX],cost[NMAX];
inline int cmp(const void *ma, const void *mb)
{
muchie a=*((muchie *)ma);
muchie b=*((muchie *)mb);
return -(a.c<b.c)+(a.c>b.c);
}
inline void adaug_st(NOD *(&prim), int x, int c)
{
NOD *a=new NOD;
a->x=x;
a->c=c;
a->adr=prim;
prim=a;
}
int root(int u)
{
if(precarb[u]<0)
return u;
return root(precarb[u]);
}
inline void uneste(int rad1, int rad2)
{
if(precarb[rad1]<precarb[rad2]) // adica rad1 are adancime mai mare decat rad2
precarb[rad2]=rad1;
else
if(precarb[rad1]>precarb[rad2]) // adica rad2 are adancime mai mare decat rad1
precarb[rad1]=rad2;
else // rad1 si rad2 au aceleasi adancimi
{
precarb[rad1]=rad2;
precarb[rad2]--;
}
}
inline int max(int x, int y)
{
return (x>y)?x:y;
}
void df(int varf, int nivel)
{
NOD *b=prim[varf];
while(b)
{
if(!vizitat[b->x])
{
vizitat[b->x]=1;
prec[b->x]=varf;
niv[b->x]=nivel+1;
cost[b->x]=b->c;
df(b->x,nivel+1);
}
b=b->adr;
}
}
int interogare(int u, int v)
{
int maxim=0;
while(niv[u]>niv[v])
{maxim=max(maxim,cost[u]);
u=prec[u];}
while(niv[u]<niv[v])
{maxim=max(maxim,cost[v]);
v=prec[v];}
while(u!=v)
{
maxim=max(maxim,cost[u]);
maxim=max(maxim,cost[v]);
u=prec[u];
v=prec[v];
}
return maxim;
}
int main()
{
int i;
fin=fopen(infile,"r");
fout=fopen(outfile,"w");
fscanf(fin,"%d %d %d",&n,&m,&k);
for(i=0;i<m;i++)
{
fscanf(fin,"%d %d %d",&mch[i].u,&mch[i].v,&mch[i].c);
mch[i].u--;
mch[i].v--;
}
qsort(mch,m,sizeof(muchie),cmp);
// Kruskal
for(i=0;i<m;i++)
used[i]=0;
for(i=0;i<n;i++)
precarb[i]=-1;
int ru,rv;
for(i=0;i<m;i++)
{
ru=root(mch[i].u);
rv=root(mch[i].v);
if(ru!=rv)
{
uneste(ru,rv);
used[i]=1;
}
}
// construire arbore
for(i=0;i<n;i++)
prim[i]=NULL;
for(i=0;i<m;i++)
if(used[i])
{
adaug_st(prim[mch[i].u],mch[i].v,mch[i].c);
adaug_st(prim[mch[i].v],mch[i].u,mch[i].c);
}
for(i=0;i<n;i++)
vizitat[i]=0;
for(i=0;i<n;i++)
if(!vizitat[i])
{
vizitat[i]=1;
prec[i]=-1;
niv[i]=0;
df(i,0);
}
// pana aici m-am descurcat in O((M+N)*logN)
// si de aici incolo o dau in bara cu complexitatea =))
int u,v;
for(i=0;i<k;i++)
{
fscanf(fin,"%d %d",&u,&v);
u--;v--;
fprintf(fout,"%d\n",interogare(u,v));
}
fclose(fin);
fclose(fout);
return 0;
}