#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize("-Ofast")
using namespace std;
mt19937_64 rng(1);
const clock_t END = 4.8 * CLOCKS_PER_SEC; ///end of execution
char *pos, BUFFER[3000001]; ///fread char buffer
inline int getnum()
{
   char C;
   while ((C = *pos++) < '0');
   int RET = C -= '0';
   while ((C = *pos++) >= '0') RET = 10 * RET + C - '0';
   return RET;
}
int N, M, K, iterations; ///the number of cities, roads, kids and optimisation iterations respectively
int HOME[1001], P[1001]; ///home cities and a permutation of kids
int SIZE[201], COST[201][2001], SORT[201][2001]; ///city sizes and cost related arrays (direct, sorted and summed)
struct EDGE
{
  int u, v, w; ///two incidental vertices and the weight of the edge between them
}E[1001]; ///roads between cities
int DIST[201][201], FROM[201][201]; ///distance between each two cities and path storing
int SUM[201], I[201]; ///cost sums and indices of cities used for scoring
ll MOMENT[2001]; ///cost of each moment
int V[2001]; ///visit status of each moment
struct DELTA
{
  int time; ///moment changed
  ll moment, score; ///changes in moment score and score
  int T[4]; ///changes in solution
}DC[1001], D[1001]; ///current and final changes
ll ScoreC, Score = 1LL << 60; ///current and final scores
int SOL[2001][4]; ///solution
inline int Length(const int *T) {return bool(T[0]) + bool(T[1]) + bool(T[2]) + bool(T[3]);} ///calculates the number of kids for given moment
inline bool Equal(const int &city, const int *T) {return (!T[0] || (T[0] == city)) && (!T[1] || (T[1] == city)) && (!T[2] || (T[2] == city)) && (!T[3] || (T[3] == city));} ///calculates whether all kids share the same home city in a given moment
inline ll Merge(const int &kid, const int &time, int *T, const bool &flag = false) ///calculates score of merging given kid into given moment
{
  int k = Length(T);
  if(k == 4) return 1LL << 60;
  int CITY[4], n = -1;
  for(int i = 0; i < k; i++) SUM[HOME[T[i]]] = 0;
  SUM[HOME[kid]] = 0;
  for(int i = 0; i < k; i++) {if(!SUM[HOME[T[i]]]) CITY[++n] = HOME[T[i]]; SUM[HOME[T[i]]] += COST[HOME[T[i]]][time];}
  if(!SUM[HOME[kid]]) CITY[++n] = HOME[kid];
  for(int i = 0; i < n; i++) for(int j = i + 1; j <= n; j++) if(CITY[j] < CITY[i]) swap(CITY[i], CITY[j]);
  SUM[HOME[kid]] += COST[HOME[kid]][time];
  ll RET = 1LL << 60, temp;
  int start = 0, sum;
  for(int i = 0; i <= n; i++) start += SUM[CITY[i]];
  do
  {
    sum = start, temp = sum * DIST[1][CITY[0]];
    for(int i = 1; i <= n; i++) {sum -= SUM[CITY[i - 1]]; temp += sum * DIST[CITY[i - 1]][CITY[i]];}
    if(temp < RET)
    {
      RET = temp;
      if(flag) for(int i = 0; i <= n; i++) I[CITY[i]] = i;
    }
  }while(next_permutation(CITY, CITY + n + 1)); ///exhaustively search all path variants
  if(flag)
  {
    T[k] = kid;
    for(int i = 0; i < k; i++) for(int j = i + 1; j <= k; j++) if(I[HOME[T[j]]] < I[HOME[T[i]]]) swap(T[i], T[j]);
    MOMENT[time] = RET;
  }
  return RET;
}
inline ll Permutation(const int &L = 1, const int &j = 0) ///calculates score for given permutation
{
  iterations++;
  ll RET = 0, temp, best;
  int moment;
  for(int i = L - 1; i >= 1; i--) ///backtracks SOL to the state it had before computing kid at index L
  {
    RET += D[i].score;
    if(V[D[i].time] != iterations) {MOMENT[D[i].time] = D[i].moment; __builtin_memcpy(SOL[D[i].time], D[i].T, 16); V[D[i].time] = iterations;}
  }
  for(int i = L; i <= K; i++) ///computes the best moments for each kid in the range [L, K]
  {
    best = 1LL << 60;
    for(int *time = SORT[HOME[P[i]]] + 1; true; time++)
    {
      if(V[*time] != iterations) {MOMENT[*time] = 0; __builtin_memset(SOL[*time], 0, 16); V[*time] = iterations;} ///this moment needs to be reset
      if((temp = (Merge(P[i], *time, SOL[*time]) - MOMENT[*time])) < best) {moment = *time; best = temp;}
      if(Equal(HOME[P[i]], SOL[*time])) break; ///no further moments can be better
    }
    Merge(P[i], moment, SOL[moment], true);
    DC[i].time = moment;
    DC[i].moment = MOMENT[moment];
    DC[i].score = best;
    __builtin_memcpy(DC[i].T, SOL[moment], 16);
    RET += best;
  }
  return RET;
}
inline void Random() ///optimises score by swapping elements in permutation P
{
  Score = Permutation();
  __builtin_memcpy(D, DC, sizeof(DELTA) * (K + 1));
  int mod = K - SIZE[1];
  while(clock() < END)
  {
    int i = (rng() % mod) + 1, j = (rng() % mod) + 1; ///arbitrary indices
    if(HOME[P[i]] == HOME[P[j]]) continue;
    if(i > j) swap(i, j);
    swap(P[i], P[j]);
    if((ScoreC = Permutation(i, j)) > Score) {swap(P[i], P[j]); continue;} ///swap was bad
    Score = ScoreC;
    __builtin_memcpy(D + i, DC + i, sizeof(DELTA) * (K - i + 1));
  }
  if(ScoreC > Score) Permutation();
  for(int i = 1; i <= 2000; i++) if(V[i] != iterations) __builtin_memset(SOL[i], 0, 16);
  cout << "Iterations: " << iterations << '\n';
  return;
}
inline void Pre() ///Floyd-Warshall and other precalculations
{
  for(int i = 1; i <= N; i++) {for(int j = 1; j <= N; j++) DIST[i][j] = 1000000007; DIST[i][i] = 0;}
  for(int i = 1; i <= M; i++)
  {
    DIST[E[i].u][E[i].v] = DIST[E[i].v][E[i].u] = E[i].w;
    FROM[E[i].u][E[i].v] = E[i].u;
    FROM[E[i].v][E[i].u] = E[i].v;
  }
  for(int k = 1; k <= N; k++)
  {
    for(int i = 1; i <= N; i++)
    {
      for(int j = 1; j <= N; j++)
      {
        if((DIST[i][k] + DIST[k][j]) >= DIST[i][j]) continue;
        DIST[i][j] = DIST[j][i] = DIST[i][k] + DIST[k][j];
        FROM[i][j] = FROM[k][j];
        FROM[j][i] = FROM[k][i];
      }
    }
  }
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= 2000; j++) SORT[i][j] = j;
    sort(SORT[i] + 1, SORT[i] + 2001, [&](const int &x, const int &y) {return COST[i][x] < COST[i][y];});
  }
  for(int i = 1, L = 1, R = K; i <= K; i++) ///makes a permutation of kids such that the ones with home city equal to one go last
  {
    SIZE[HOME[i]]++;
    if(HOME[i] != 1) P[L++] = i;
    else P[R--] = i;
  }
  return;
}
inline void Input() ///inputs test data
{
  freopen("transport.in", "r", stdin);
  fread(pos = BUFFER, 1, 3000000, stdin);
  N = getnum(), M = getnum(), K = getnum();
  for(int i = 1; i <= K; i++) HOME[i] = getnum();
  for(int i = 1; i <= N; i++) for(int j = 1; j <= 2000; j++) COST[i][j] = getnum();
  for(int i = 1; i <= M; i++) E[i].u = getnum(), E[i].v = getnum(), E[i].w = getnum();
  return;
}
inline void Output() ///outputs solution
{
  freopen("transport.out", "w", stdout);
  int tours = 0, k;
  queue <int> Q;
  auto Path = [&](int u, int v)
  {
    while(u != v) {Q.push(u); u = FROM[v][u];}
    return;
  };
  for(int i = 1; i <= 2000; i++) tours += bool(Length(SOL[i]));
  printf("%d\n", tours);
  for(int i = 1; i <= 2000; i++)
  {
    k = Length(SOL[i]);
    if(!k) continue;
    Path(1, HOME[SOL[i][0]]);
    for(int j = 1; j < k; j++) Path(HOME[SOL[i][j - 1]], HOME[SOL[i][j]]);
    Q.push(HOME[SOL[i][k - 1]]);
    printf("%d %d %d\n", i, k, Q.size());
    for(int j = 0; j < k; j++) printf("%d%c", SOL[i][j], " \n"[j == (k - 1)]);
    while(Q.size()) {printf("%d%c", Q.front(), " \n"[Q.size() == 1]); Q.pop();}
  }
  return;
}
int main()
{
  Input();
  Pre();
  Random();
  cout << "Final: " << Score << '\n';
  Output();

  return 0;
}