program Cuu_tro;
const inf='BAI3.INP';
      outF='BAI3.OUT';
      MAXn=100;
type      lent=array[2..maxN] of longword;
VAR D:array[1..MaxN,1..maxN] of integer;
    DT:array[1..2] of lent;
    truoc,sau,n:byte;

{**************************************}
procedure Enter;
var i,u,v,k,m:byte;W:integer;  f:TEXT;
begin
assign(F,inf);
reset(f);
readln(F,n,k,m);
for i:=1 to k do
  begin
      readln(F,u,v,w);
      D[u,v]:=W;
      D[v,u]:=W;
  end;
for i:=1 to m do
  begin
      readln(F,u,v);
      D[u,v]:=0;
      D[v,u]:=0;
  end;
close(f);
end;
{****************************************}
procedure Go;
var x,y:byte;  co:boolean;
begin
truoc:=1;sau:=2;co:=false;
fillchar(DT,sizeof(DT),0);
  {di tu nut 1}
  for x:=2 to n do
    if D[1,x]>0 then
        begin
            DT[truoc,x]:=D[1,x];
            co:=true;
        end;
  while co=true do
    begin
        co:=false;
        for x:=2 to n do
          if DT[truoc,x]>0 then  {no da di toi}
              for y:= 2 to n do
                if x=y then DT[sau,x]:=DT[truoc,y] else
                if D[x,y]>0 then  {co duong d tu x toi y}
                begin
                  if (DT[sau,y]=0) then  {chua di toi}
                    begin
                    DT[sau,y]:=DT[truoc,x]+D[x,y];
                    co:=true; {con di duoc}
                    end else  {da toi}
                  if  DT[truoc,x]+D[x,y]< DT[sau,y] then
                    begin
                          co:=true;
                          DT[sau,y]:=DT[truoc,x]+D[x,y];
                    end;
                end;
    if truoc=1 then begin truoc:=2;sau:=1; end else begin truoc:=1; sau:=2;end;
    end;
end;
{*************************************************}
procedure result;
var f:text;i:byte;
begin
 asSign(f,outF);
 rewrite(F);
 for i:=2 to n do
  if DT[truoc,i]>0 then  writeln(F, i,' ',DT[truoc,i]) else writeln(F,i,'  khong co');
 close(F);
end;

begin
ENTER;
GO;
RESULT;
end.

const max = 200000;
var n,ki:longint;
    a:array[1..max] of longint;
    b:array[1..max] of longint;
    sl,so:array[1..max] of longint;
    f1,f2:text;
procedure nhap;
var i:longint;
 begin
 assign(f1,'so1.inp'); reset(f1);
 readln(f1,n);
 for i:=1 to n do
  read(f1,a[i]);
 end;
procedure sapxep;
var i,j,t:longint;
 begin
 for i:=1 to n-1 do
  for j:=i+1 to n do
  if a[i]>a[j] then
    begin
    t:=a[j];
    a[j]:=a[i];
    a[i]:=t;
    end;
  end;
procedure xuly;
var h,i:longint;
 begin
    i:=1; ki:=0;
    repeat
    h:=a[i];
    inc(ki);
    so[ki]:=h;
    while h=a[i] do
      begin
      inc(sl[ki]);
      inc(i);
      end;
    until i>n;
  end;
procedure xuat;
var i:longint;
 begin
 assign(f2,'so1.out');  rewrite(f2);
 writeln(n);
 writeln(f2,ki);
 for i:=1 to ki do
  writeln(f2,so[i],' ',sl[i]);
  close(f2);
 end;
begin
nhap;
sapxep;
xuly;
xuat;
end.