#include <iostream>
//floyd warshall with path

using namespace std;

struct adjprev
{
  int a;
  int prev;

};

adjprev adj[10000][10000];

int main()
{
    int v,e,temp1,temp2,w,q;
    cin>>v>>e>>q;
    for(int i=0;i<v;i++)
    {
        for(int j=0;j<v;j++)//initiating with infinity
        {
            adj[i][j].a=100000;
        }
        adj[i][i].a=0; //if they are equal
        adj[i][i].prev=i;
    }
    for(int i=0;i<e;i++) //initiating all edges
    {
        cin>>temp1>>temp2>>w;
        temp1--;
        temp2--;
        adj[temp1][temp2].a=w;
    }

    for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
    for(int j=0;j<v;j++)
       {
           if(i==j)
           {
               continue;
           }
           //adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
           if(adj[i][j].a>(adj[i][k].a+adj[k][j].a))
           {
               adj[i][j].a=adj[i][k].a+adj[k][j].a; //replacing
               adj[i][j].prev=k;
           }
       }

 // for(int i=0;i<v;i++)
   // {
      // for(int j=0;j<v;j++)
      // {
          //  cout<<i<<"  "<<j<<"   "<<adj[i][j].a<<endl; //cout all shortest paths;
       // }
   // }
    for(int i=0;i<q;i++)
   {
       cin>>temp1>>temp2;
        temp1--;
        temp2--;
        cout<<adj[temp1][temp2].a<<endl;
        cout<<endl;
        cout<<temp2+1<<endl;
      while(temp1!=temp2)
          {
           cout<<adj[temp1][temp2].prev+1<<endl;
           temp2=adj[temp1][temp2].prev-1;
         }
    }








}