#include <bits/stdc++.h>
# define clr(x,a)        memset(x,a,sizeof(x))
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define deb2(x, y)      cout<<"("<<#x<<", "<<#y<<")==("<<x<<", "<<y<<")\n";
# define pb              push_back
# define sc              scanf
# define pr              printf
# define nd              second
# define tc              int t; cin>>t; while(t--)
# define rev(s)          reverse(s.begin(),s.end())
# define linija          cout<<"___________\n";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mxN=205, mxM=1005, mxG = 1005;
const ll INF = 1e16;
const int inf = 1e8;

int n, m, g, home[mxG];
int cost[mxG][2005];
vector<vector<ll>> cost_matrix;
vector<pii> graf[mxN];
int dist[mxN][mxN];
int glob_cities[5], next_city;

struct Output_route{
   int moment, child_cnt, city_cnt;
   int children[4];
   vi route;
   bool operator < (const Output_route& R) const{
      return moment < R.moment;
   }
   inline void output_route(){
      pr("%d %d %d\n", moment, child_cnt, city_cnt);
      for(int i = 0; i < child_cnt; i++) pr("%d ", children[i]);
      cout << "\n";
      for(int city: route) pr("%d ", city);
      cout << "\n";
   }
};

struct Solution{
   Output_route sol[mxM];
   ll score;
   int route_cnt;

   void init(){
      route_cnt = 0;
      score = 0;
   }
   void add(Output_route r){
      sol[++route_cnt] = r;
   }
   void sort_time_increasing(){
      sort(sol+1, sol+1+route_cnt);
   }
}sol, temp;

struct IO{
   void input(){
      freopen("transport.in", "r", stdin);
      sc("%d %d %d", &n, &m, &g);
      for(int i = 1; i <= g; i++){
         sc("%d", &home[i]);
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= 2000; j++){
            sc("%d", &cost[i][j]);
         }
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n; j++)
            dist[i][j] = inf;
         dist[i][i] = 0;
      }

      int u, v, w;
      for(int i = 1; i <= m; i++){
         sc("%d %d %d", &u, &v, &w);
         dist[u][v] = dist[v][u] = w;
         graf[u].pb(make_pair(v, w));
         graf[v].pb(make_pair(u, w));
      }
   }

   void output(){
      sol.sort_time_increasing();
      freopen("transport.out", "w", stdout);
      pr("%d\n", sol.route_cnt);
      for(int i = 1; i <= sol.route_cnt; i++)
         sol.sol[i].output_route();
   }
}io;

//gpt code
class Hungarian {
public:
    Hungarian(const vector<vector<ll>>& cost)
        : n(cost.size()), cost(cost), label_row(n, 0), label_col(n, 0),
          match_row(n, -1), match_col(n, -1), slack(n), slack_row(n), prev(n) {}

    ll solve() {
        // Step 1: Init labels
        for (int i = 0; i < n; ++i)
            label_row[i] = *min_element(cost[i].begin(), cost[i].end());

        for (int i = 0; i < n; ++i)
            augment(i);

        int result = 0;
        for (int i = 0; i < n; ++i)
            result += cost[i][match_row[i]];

        return result;
    }

    vector<int> get_assignment() {
        return match_row;
    }

private:
    int n;
    vector<vector<ll>> cost;
    vector<ll> label_row, label_col;
    vector<int> match_row, match_col;
    vector<ll> slack, slack_row, prev;

    void augment(int start) {
        vector<bool> visited_row(n, false), visited_col(n, false);
        vector<int> min_slack_col(n, 0);

        int root = start;
        prev.assign(n, -1);
        for (int j = 0; j < n; ++j) {
            slack[j] = cost[root][j] - label_row[root] - label_col[j];
            slack_row[j] = root;
        }

        int col = -1;
        while (true) {
            int delta = INF;
            for (int j = 0; j < n; ++j) {
                if (!visited_col[j] && slack[j] < delta) {
                    delta = slack[j];
                    col = j;
                }
            }

            for (int i = 0; i < n; ++i)
                if (visited_row[i]) label_row[i] += delta;

            for (int j = 0; j < n; ++j) {
                if (visited_col[j]) label_col[j] -= delta;
                else slack[j] -= delta;
            }

            visited_col[col] = true;
            int row = match_col[col];
            if (row == -1) {
                while (col != -1) {
                    int prev_col = match_row[slack_row[col]];
                    match_row[slack_row[col]] = col;
                    match_col[col] = slack_row[col];
                    col = prev_col;
                }
                return;
            }

            visited_row[row] = true;
            for (int j = 0; j < n; ++j) {
                if (!visited_col[j]) {
                    int new_slack = cost[row][j] - label_row[row] - label_col[j];
                    if (new_slack < slack[j]) {
                        slack[j] = new_slack;
                        slack_row[j] = row;
                    }
                }
            }
        }
    }
};

void floyd_warhsal(){
   for(int k = 1; k <= n; k++){
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n; j++){
            dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
         }
      }
   }
}

struct Route{
   int cities[4], citizens[4];

   void output(){
      for(int i = 0; i < 4; i++){
         if(cities[i] == 0) continue;
         cout << cities[i] << " ";
      }
      cout << endl;
      for(int i = 0; i < 4; i++){
         if(citizens[i] == 0) continue;
         cout << citizens[i] << " ";
      }
      cout << endl;
      cout << endl;
   }
}routes[mxG], pom_route;

vi citizens_at_home[mxN];
int num_routes;

inline void put_cities(const int num_citizens, const int& city){
   num_routes++;
   for(int j = 0; j < num_citizens; j++){
      routes[num_routes].cities[j] = city;
      routes[num_routes].citizens[j] = citizens_at_home[city][j];
   }
}

void all_in_one_city(){
   for(int i = 1; i <= n; i++){
      if(citizens_at_home[i].size() == 1) continue;

      while(citizens_at_home[i].size() > 6){
         put_cities(4, i);
         citizens_at_home[i].erase(citizens_at_home[i].begin(), citizens_at_home[i].begin() + 4);
      }

      if(citizens_at_home[i].size() >= 5){
         put_cities(3, i);
         citizens_at_home[i].erase(citizens_at_home[i].begin(), citizens_at_home[i].begin() + 3);
      }

      put_cities(citizens_at_home[i].size(), i);
      citizens_at_home[i].clear();
   }
}

int find_solo_citizen(){
   for(int i = 1; i <= g; i++){
      if(citizens_at_home[i].size())
         return citizens_at_home[i][0];
   }

   return -1; //shouldn't happen
}

void fix_left_citizens(int& left_citizens){
   //all citizens that have to go to city, but they are solo
   if(left_citizens == 1){
      vi candidates;

      //search for candidats (routes that have less than 4 cities)
      for(int i = 1; i <= num_routes; i++){
         if(routes[i].cities[3] == 0){
            candidates.pb(i);
         }
      }

      int best = inf, route_id;
      int my_citizen = find_solo_citizen();


      //no candidate, some route must break
      if(candidates.size() == 0){
         for(int i = 1; i <= num_routes; i++){
            if(dist[home[my_citizen]][routes[i].cities[0]] < best){
               best = dist[home[my_citizen]][routes[i].cities[0]];
               route_id = i;
            }
         }
         //deleting one tick of existing route (last)
         routes[route_id].cities[3] = routes[route_id].citizens[3] = 0;

         //adding new route, with best city, citizen, and solo city, citizen
         num_routes++;
         routes[num_routes].cities[0] = routes[route_id].cities[2];
         routes[num_routes].citizens[0] = routes[route_id].citizens[2];

         routes[num_routes].cities[1] = home[my_citizen];
         routes[num_routes].citizens[1] = my_citizen;
      }
      else{
         for(int i: candidates){
            if(dist[home[my_citizen]][routes[i].cities[0]] < best){
               best = dist[home[my_citizen]][routes[i].cities[0]];
               route_id = i;
            }
         }

         //index for city, citizen to put INSIDE route_id
         int idc = 3;
         if(routes[route_id].cities[2] == 0) idc = 2;

         //adding tick to existing route
         routes[route_id].cities[idc] = home[my_citizen];
         routes[route_id].citizens[idc] = my_citizen;
      }

      return;
   }

   if(left_citizens >= 9) exit(10);

   vi citizens;
   for(int i = 1; i <= g; i++){
      if(citizens_at_home[i].size() == 1){
         citizens.pb(i);
      }
   }

}

void make_routes(){
   for(int i = 1; i <= g; i++)
      citizens_at_home[home[i]].pb(i);

   all_in_one_city();

   int left_citizens = 0;
   for(int i = 1; i <= g; i++){
      if(citizens_at_home[i].size() == 1){
         left_citizens++;
      }
   }

   if(left_citizens > 0)
      fix_left_citizens(left_citizens);

   for(int i = 1; i <= num_routes; i++){
      //routes[i].output();
   }
   //cout << endl;
}

void make_cost_matrix(){

}

void hungarian_sheduling(){
   Hungarian hungarian(cost_matrix);
   int result = hungarian.solve();
   std::vector<int> assignment = hungarian.get_assignment();

   std::cout << "Minimum cost: " << result << "\n";
   for (int i = 0; i < assignment.size(); ++i) {
      std::cout << "Row " << i << " assigned to column " << assignment[i] << "\n";
   }
}

void solve(){
   floyd_warhsal();
   make_routes();
   make_cost_matrix();
   hungarian_sheduling();
}

int main(){
   io.input();

   solve();

   io.output();

   return 0;
}