//#include <bits/stdc++.h>
#include <iostream>
#include <time.h>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <chrono>
#include <random>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <limits>
#include <cmath>
#include <thread>

#define endl '\n'
#define X first
#define Y second
#define MAXN 262144
#define MAXV 1048576
#define INF 1000010000
#define LLINF 1000000100000000
#define ULLINF 100000001000000
#define MOD 1000000007
#define control cout<<" passed "<<'\n';
#define ENTER cout<<endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef pair <int,int> pii;
typedef vector <long long> vll;
typedef vector <unsigned long long> vull;
typedef vector <string> vs;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}











int n;
int m;
int g;
vector <pii> hometown;
int depth[2048];
vector <pii> v[256];
int r[256];
int dist1[2048];
int d[13172];
vector <int> nope[2048];
bool cmphtown(pii a,pii b)
{
    /*if(d[a.Y]<d[b.Y])return true;
    return false;*/
    /*if(dist1[a.Y]==dist1[b.Y])
    {
        if(d[a.Y]<d[b.Y])return true;
        //return false;
    }
    if(dist1[a.Y]<=4&&dist1[b.Y]<6&&dist1[a.Y]>=4||dist1[a.Y]==4&&dist1[b.Y]>6)return false;
    if(dist1[a.Y]<=4||dist1[b.Y]<=4)if(depth[a.Y]>depth[b.Y])return true;*/


    if(dist1[a.Y]>dist1[b.Y])return true;
    if(dist1[a.Y]==dist1[b.Y])
    {
        /*if(r[r[r[a.Y]]]!=0&&r[r[r[b.Y]]]!=0&&nope[a.Y].size()+nope[r[a.Y]].size()+nope[r[r[a.Y]]].size()>=4&&nope[b.Y].size()+nope[r[b.Y]].size()+nope[r[r[b.Y]]].size()>=4)
        {
            if(d[r[r[r[a.Y]]]]>d[r[r[r[b.Y]]]])return true;
            return false;
        }
        else if(r[r[a.Y]]!=0&&r[r[b.Y]]!=0&&nope[a.Y].size()>=3&&nope[b.Y].size()>=3&&nope[r[a.Y]].size()>=1&&nope[r[b.Y]].size()>=1)
        {
            if(d[r[r[a.Y]]]>d[r[r[b.Y]]])return true;
            return false;
        }
        else if(r[a.Y]!=0&&r[b.Y]!=0&&nope[a.Y].size()>=4&&nope[b.Y].size()>=4)
        {
            if(d[r[a.Y]]>d[r[b.Y]])return true;
            return false;
        }*/
        if(d[a.Y]>d[b.Y])return true;
        return false;
    }
    return false;
}

int usedfs[2048];
void bfs(int beg)
{
    /*for(int i=1;i<=n;i++)
    {
        r[i].push_back(1);
    }*/
    queue <int> q;
    usedfs[beg]=1;
    q.push(beg);
    while(!q.empty())
    {
        auto w=q.front();
        q.pop();
        for(auto c:v[w])
        {
            if(!usedfs[c.X])
            {
                q.push(c.X);
                /*for(int i=0;i<r[w].size();i++)
                {
                    int nb=r[w][i];
                    r[c.X].push_back(nb);
                }
                r[c.X].push_back(w);*/
                usedfs[c.X]=1;
                depth[c.X]=depth[w]+1;
            }
        }
    }
}

bool usedd[13172];


void dijkstra(int beg)
{
    memset(d,INF,sizeof(d));
    d[1]=0;
    dist1[1]=1;
    priority_queue<pii> pq;
    pii e={0,beg};
    pq.push(e);
    while(!pq.empty())
    {
        e=pq.top();
        e.X*=-1;//control;
        pq.pop();
        //if(d[e.X]<e.Y)continue;
        if(usedd[e.Y]==1)continue;
        usedd[e.Y]=1;
        int sz=v[e.Y].size();
        for(int i=0;i<sz;i++)
        {
            pii nb=v[e.Y][i];
            //cout<<nb.p<<" "<<INF<<endl;
            if(d[nb.X]>d[e.Y]+nb.Y)
            {
                nb.Y=d[e.Y]+nb.Y;
                d[nb.X]=nb.Y;
                auto c=nb;
                r[c.X]=e.Y;
                dist1[c.X]=dist1[e.Y]+1;
            }
            int nzz=nb.X;
            int nzzz=nb.Y;
            nb.Y=nzz;
            nb.X=nzzz;
            nb.X*=-1;
            /*else if(d[nb.v]==max(d[e.v],nb.p)&&d1[nb.v]>d1[e.v]+nb.w)
            {
                d1[e.v]=d1[e.v]+nb.w;
            }*/
            pq.push(nb);
        }
    }
}

int cost[2048][2048];

int ab[2048];




void read()
{
    memset(ab,INF,sizeof(ab));
    //r[1].push_back(1);
    cin>>n;
    cin>>m;
    cin>>g;
    for(int i=1;i<=g;i++)
    {
        int x;
        cin>>x;
        nope[x].push_back(i);
        hometown.push_back({i,x});
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2000;j++)
        {
            cin>>cost[i][j];
            ab[i]=min(ab[i],cost[i][j]);
        }
    }
    bool us[13072];
    memset(us,0,sizeof(us));
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        pii p;
        p.X=y;
        p.Y=c;
        v[x].push_back(p);
        p.X=x;
        p.Y=c;
        v[y].push_back(p);

        /*if(x==1)
        {
            r[y].push_back(x);
        }
        else if(y==1)
        {
            r[x].push_back(y);
        }
        else*/
    }
    bfs(1);
    dijkstra(1);
    /*for(auto w:hometown)
    {
        cout<<w.second<<" ";
    }ENTER;*/
    ///Shuffle(hometown);
    //sort(hometown.begin(),hometown.end(),cmphtown);

    for(int i=0;i<hometown.size();i++)
    {
        for(int j=0;j<hometown.size();j++)
        {
            if(i==j)continue;
            if(cmphtown(hometown[i],hometown[j]))swap(hometown[i],hometown[j]);
        }
    }

    /*for(auto w:r[3])
    {
        cout<<w<<" ";
    }ENTER;*/
}

vector <vector<int>> ans;
int used[13172];
int moment[2048];
bool comp(vi a,vi b)
{
    if(a[0]<b[0])return true;
    else return false;
}

bool cmp(pair<pii,int> a, pair <pii,int> b)
{
    if(a.Y>b.Y)return true;
    return false;
}

int minn(int c,int c1,int c2)
{
    int mi=INF;
    for(int i=1;i<=2000;i++)
    {
        ll sum=0;
        sum+=cost[c][i];
        sum+=cost[c1][i];
        sum+=cost[c2][i];
        if(sum<mi&&moment[i]==0)
        {
            mi=sum;
        }
    }
    return mi;
}
int costt(vector <int> path,int k1,int k2,int time)
{
    int last=1;
    int sum=cost[k1][time]+cost[k2][time];
    int tcost=0;
    for(auto w:path)
    {

        tcost+=sum*min((d[w]-d[last]),1);
        last=w;
        if(w==k1)
        {
            sum=cost[k2][time];
        }
    }
    return tcost;
}
int costtt(vector <int> path,int k1,int k2,int k3,int k4,int time)
{
    int last=1;
    int sum=cost[k1][time]+cost[k2][time]+cost[k3][time]+cost[k4][time];
    int tcost=0;
    for(auto w:path)
    {
        tcost+=sum*max(abs(d[w]-d[last]),1);
        last=w;
        if(w==k1)
        {
            sum-=cost[k1][time];
        }
        if(w==k2)
        {
            sum-=cost[k2][time];
        }
        if(w==k3)
        {
            sum-=cost[k3][time];
        }
        if(w==k4)
        {
            sum-=cost[k4][time];
        }
    }
    return tcost;
}
void solve()
{
    read();
    //return;
    int ha=0;
    int okk=1;
    /*for(auto w:hometown)
    {
        cout<<w.Y<<" ";
    }cout<<endl;*/
    int tes=4;

    int grad=hometown[0].Y;

    /*int fakeused[131072];
    memset(fakeused,0,sizeof(fakeused));
    vector <pair<pair<int,int>,int>> vec;
    for(auto w:hometown)
    {
        //if(grad!=w.Y)break;
        if(fakeused[w.X]==1)continue;
        vector <int> backt;

        int brn=2;
        vector <int> nk;
        //nk.push_back(w.X);
        //used[w.X]=1;
        int ce=w.Y;
        backt.push_back(w.Y);
        if(w.Y!=1)
        {
            do
            {
                backt.push_back(r[ce]);
                ce=r[ce];
            }while(ce!=1);
        }
        vector <int> tungtung;
        //reverse(backt.begin(),backt.end());
        if(tes==4)if(backt.size()<2)continue;

        bool lampar=0;

        vector <int> usink;
        vector <int> usink2;
        ll mee=INF;
        usink.push_back(w.Y);
        usink2.push_back(w.X);
        fakeused[w.X]=1;

        int lasttown=w.Y;
        for(int i=0;i<backt.size();i++)
        {
            int c=backt[i];
            bool lam=0;
            for(auto brbrrpat:nope[c])
            {
                if(brbrrpat==w.X)continue;
                if(usink.size()>=4)break;
                if(fakeused[brbrrpat]==0)
                {
                    fakeused[brbrrpat]=1;
                    lam=1;
                    usink2.push_back(brbrrpat);
                    usink.push_back(c);
                }
            }
            if(lam)lasttown=c;
            if(lam==0)
            {
                break;
            }
            if(usink.size()>=4)break;

        }


        pair<pair<int,int>,int> pi;
        pi.X.X=w.X;
        pi.X.Y=w.Y;
        pi.Y=d[lasttown];
        vec.push_back(pi);
        continue;

        ///if(tes==4&&usink.size()<4)continue;
        ///if(tes==3&&usink.size()<3)continue;
        ///if(tes==2&&usink.size()<2)continue;
        int momenta;
        if(lampar)continue;
        ll costN=INF;
        bool lampi=0;
        int el=0;
        for(auto c:usink)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }
        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                if(usink.size()==4){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]]&&cost[usink[2]][i]<=ab[usink[2]]&&cost[usink[3]][i]<=ab[usink[3]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=4;
                }}
                if(usink.size()>=3){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]]&&cost[usink[2]][i]<=ab[usink[2]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=3;
                }}
                if(usink.size()>=2){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=2;
                }}
                if(usink.size()>=1){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=1;
                }}
            }
        }
        if(lampi==0)continue;
        int br=0;
        for(auto c:usink2)
        {
            br++;
            if(br>el)break;
            nk.push_back(c);
        }
        reverse(backt.begin(),backt.end());
        moment[momenta]=1;
        okk=momenta;
        vector <int> nik;
        //cout<<okk<<" "<<)<<" "<<<<endl;
        nik.push_back(okk);
        nik.push_back(nk.size());
        nik.push_back(backt.size());
        ha++;
        for(auto gi:nk)
        {
            //if(used[gi]==1)lampat=1;
            nik.push_back(gi);
            used[gi]=1;
        }
        for(auto c:backt)
        {
            nik.push_back(c);
        }
        //nik.push_back(d[w.Y]);
        ans.push_back(nik);
    }

    sort(vec.begin(),vec.end(),cmp);
    cout<<vec[0].Y<<" "<<vec[1].Y<<" "<<vec[2].Y<<endl;
    for(auto skibidi:vec)
    {
        pii w=skibidi.X;
        if(grad!=w.Y)continue;
        if(used[w.X]==1)continue;
        vector <int> backt;
        int brn=2;
        vector <int> nk;
        int ce=w.Y;
        backt.push_back(w.Y);
        if(w.Y!=1)
        {
            do
            {
                backt.push_back(r[ce]);
                ce=r[ce];
            }while(ce!=1);
        }
        vector <int> tungtung;
        //reverse(backt.begin(),backt.end());
        //if(tes==4)if(backt.size()<2)continue;

        bool lampar=0;

        vector <int> usink;
        vector <int> usink2;
        ll mee=INF;
        usink.push_back(w.Y);
        usink2.push_back(w.X);

        for(int i=0;i<backt.size();i++)
        {
            int c=backt[i];
            bool lam=0;
            for(auto brbrrpat:nope[c])
            {
                if(brbrrpat==w.X)continue;
                if(usink.size()>=4)break;
                if(used[brbrrpat]==0)
                {
                    ///used[brbrrpat]=1;
                    lam=1;
                    usink2.push_back(brbrrpat);
                    usink.push_back(c);
                }
            }
            if(lam==0)
            {
                break;
            }
            if(usink.size()>=4)break;

        }



        ///if(tes==4&&usink.size()<4)continue;
        ///if(tes==3&&usink.size()<3)continue;
        //if(tes==2&&usink.size()<2)continue;
        int momenta;
        //if(lampar)continue;
        ll costN=INF;
        bool lampi=0;
        int el=0;
        for(auto c:usink)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }
        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                if(usink.size()==4){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]]&&cost[usink[2]][i]<=ab[usink[2]]&&cost[usink[3]][i]<=ab[usink[3]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=4;
                }}
                if(usink.size()>=3){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]]&&cost[usink[2]][i]<=ab[usink[2]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=3;
                }}
                if(usink.size()>=2){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]&&cost[usink[1]][i]<=ab[usink[1]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=2;
                }}
                if(usink.size()>=1){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]])
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    el=1;
                }}
            }
        }
        if(lampi==0)continue;
        int br=0;
        for(auto c:usink2)
        {
            br++;
            if(br>el)break;
            nk.push_back(c);
        }
        reverse(backt.begin(),backt.end());
        moment[momenta]=1;
        okk=momenta;
        vector <int> nik;
        //cout<<okk<<" "<<)<<" "<<<<endl;
        nik.push_back(okk);
        nik.push_back(nk.size());
        nik.push_back(backt.size());
        ha++;
        for(auto gi:nk)
        {
            //if(used[gi]==1)lampat=1;
            nik.push_back(gi);
            used[gi]=1;
        }
        for(auto c:backt)
        {
            nik.push_back(c);
        }
        //nik.push_back(d[w.Y]);
        ans.push_back(nik);
    }*/






    while(tes--){
    for(auto w:hometown)
    {
        if(used[w.X]==1)continue;
        vector <int> backt;
        int pe=w.Y;
        int brn=2;
        vector <int> nk;
        int ce=w.Y;
        backt.push_back(w.Y);
        if(w.Y!=1)
        {
            do
            {
                backt.push_back(r[ce]);
                ce=r[ce];
            }while(ce!=1);
        }
        vector <int> tungtung;
        if(tes==4)if(backt.size()<2)continue;

        bool lampar=0;

        vector <int> usink;
        vector <int> usink2;
        ll mee=INF;
        usink.push_back(w.Y);
        usink2.push_back(w.X);
        int brg=1;
        for(int i=0;i<backt.size();i++)
        {
            int c=backt[i];
            bool lam=0;
            for(auto brbrrpat:nope[c])
            {
                if(brbrrpat==w.X)continue;
                if(usink.size()>=4)break;
                if(used[brbrrpat]==0)
                {
                    lam=1;
                    usink2.push_back(brbrrpat);
                    usink.push_back(c);
                }
            }
            if(lam&&c!=w.Y)brg++;
            if(lam==0)
            {
                break;
            }
            if(usink.size()>=4)break;

        }
        if(tes==4&&usink.size()<4)continue;
        if(tes==3&&usink.size()<3)continue;
        if(tes==2&&usink.size()<2)continue;
        int momenta;
        if(lampar)continue;
        ll costN=INF;
        bool lampi=0;
        int ele=0;
        for(auto c:usink)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }

        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                int be=0;
                if(brg==2)be=0;
                else if(brg==3)be=0;
                if(brg==4)be=0;
                if(usink.size()==4){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be&&cost[usink[3]][i]<=ab[usink[3]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=4;
                }}
                if(usink.size()>=3){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=3;
                }}
                if(usink.size()>=2){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=2;
                }}
                if(usink.size()>=1){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=1;
                }}
            }
        }
        int biggest=w.X;
        int biggest2=w.Y;

        for(auto el:hometown)
        {
            if(clock()>4000)continue;
            if(el.X==w.X)continue;
            if(used[el.X]==1)continue;
            if(used[w.X]==1)continue;
            vector <int> backtt;
            int brnn=2;
            int cee=w.Y;
            backtt.push_back(w.Y);
            if(el.Y!=1)
            {
                do
                {
                    backtt.push_back(r[cee]);
                    cee=r[cee];
                }while(cee!=1);
        }
        //if(backtt.size()<2)continue;

        bool lamparr=0;

        vector <int> usinkk;
        vector <int> usinkk2;
        ll meee=INF;
        usinkk.push_back(el.Y);
        usinkk2.push_back(el.X);
        int brgg=1;
        for(int i=0;i<backtt.size();i++)
        {
            int cc=backtt[i];
            bool lamm=0;
            for(auto brbrrpat:nope[cc])
            {
                if(brbrrpat==el.X)continue;
                if(usinkk.size()>=4)break;
                if(used[brbrrpat]==0)
                {
                    lamm=1;
                    usinkk2.push_back(brbrrpat);
                    usinkk.push_back(cc);
                }
            }
            if(lamm&&cc!=el.Y)brgg++;
            if(lamm==0)
            {
                break;
            }
            if(usinkk.size()>=4)break;

        }
        //if(tes==4&&usinkk.size()<4)continue;
        //if(tes==3&&usinkk.size()<3)continue;
        //if(tes==2&&usinkk.size()<2)continue;
        int momentaa=0;
        if(lamparr)continue;
        ll costtN=INF;
        bool lampii=0;
        int ele=0;
        for(auto c:usinkk)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }

        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                int be=0;
                if(brgg==2)be=0;
                else if(brgg==3)be=0;
                if(brgg==4)be=0;
                if(usinkk.size()==4){
                if(sum<costN&&cost[usinkk[0]][i]<=ab[usinkk[0]]+be&&cost[usinkk[1]][i]<=ab[usinkk[1]]+be&&cost[usinkk[2]][i]<=ab[usinkk[2]]+be&&cost[usinkk[3]][i]<=ab[usinkk[3]]+be)
                {
                    lampii=1;
                    costtN=sum;
                    momentaa=i;
                    ele=4;
                }}
                if(usinkk.size()>=3){
                if(sum<costN&&cost[usinkk[0]][i]<=ab[usinkk[0]]+be&&cost[usinkk[1]][i]<=ab[usinkk[1]]+be&&cost[usinkk[2]][i]<=ab[usinkk[2]]+be)
                {
                    lampii=1;
                    costtN=sum;
                    momentaa=i;
                    ele=3;
                }}
                if(usinkk.size()>=2){
                if(sum<costN&&cost[usinkk[0]][i]<=ab[usinkk[0]]+be&&cost[usinkk[1]][i]<=ab[usinkk[1]]+be)
                {
                    lampii=1;
                    costtN=sum;
                    momentaa=i;
                    ele=2;
                }}
                if(usinkk.size()>=1){
                if(sum<costN&&cost[usinkk[0]][i]<=ab[usinkk[0]]+be)
                {
                    lampii=1;
                    costtN=sum;
                    momentaa=i;
                    ele=1;
                }}
            }
        }
        if(lampii==0)continue;
        if(momentaa==momenta)
        {
            if(d[w.Y]<d[el.Y])
            {
                biggest=el.X;
                biggest2=el.Y;
            }
        }

        }


        /*if(biggest!=w.X)
        {
            if(used[biggest]==1)continue;
        backt.clear();
        int brn=2;
        nk.clear();
        ce=biggest2;
        backt.push_back(biggest2);
        if(biggest2!=1)
        {
            do
            {
                backt.push_back(r[ce]);
                ce=r[ce];
            }while(ce!=1);
        }
        //if(tes==4)if(backt.size()<2)continue;

        bool lampar=0;

        usink.clear();
        usink2.clear();
        ll mee=INF;
        usink.push_back(w.Y);
        usink2.push_back(w.X);
        brg=1;
        for(int i=0;i<backt.size();i++)
        {
            int c=backt[i];
            bool lam=0;
            for(auto brbrrpat:nope[c])
            {
                if(brbrrpat==w.X)continue;
                if(usink.size()>=4)break;
                if(used[brbrrpat]==0)
                {
                    lam=1;
                    usink2.push_back(brbrrpat);
                    usink.push_back(c);
                }
            }
            if(lam&&c!=w.Y)brg++;
            if(lam==0)
            {
                break;
            }
            if(usink.size()>=4)break;

        }
        if(tes==4&&usink.size()<4)continue;
        if(tes==3&&usink.size()<3)continue;
        if(tes==2&&usink.size()<2)continue;
        momenta=0;
        if(lampar)continue;
        costN=INF;
        lampi=0;
        ele=0;
        for(auto c:usink)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }

        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                int be=0;
                if(brg==2)be=0;
                else if(brg==3)be=0;
                if(brg==4)be=0;
                if(usink.size()==4){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be&&cost[usink[3]][i]<=ab[usink[3]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=4;
                }}
                if(usink.size()>=3){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=3;
                }}
                if(usink.size()>=2){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=2;
                }}
                if(usink.size()>=1){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=1;
                }}
            }
        }
        }*/

        if(lampi==0)continue;
        int brrr=0;
        for(auto c:usink2)
        {
            brrr++;
            if(brrr>ele)break;
            nk.push_back(c);
        }
        reverse(backt.begin(),backt.end());
        moment[momenta]=1;
        okk=momenta;
        vector <int> nik;
        //cout<<okk<<" "<<)<<" "<<<<endl;
        nik.push_back(okk);
        nik.push_back(nk.size());
        nik.push_back(backt.size());
        ha++;
        for(auto gi:nk)
        {
            //if(used[gi]==1)lampat=1;
            nik.push_back(gi);
            used[gi]=1;
        }
        for(auto c:backt)
        {
            nik.push_back(c);
        }
        //nik.push_back(d[w.Y]);
        ans.push_back(nik);
    }}


    tes=4;
    while(tes--){
    for(auto w:hometown)
    {
        if(used[w.X]==1)continue;
        vector <int> backt;
        int pe=w.Y;
        int brn=2;
        vector <int> nk;
        int ce=w.Y;
        backt.push_back(w.Y);
        if(w.Y!=1)
        {
            do
            {
                backt.push_back(r[ce]);
                ce=r[ce];
            }while(ce!=1);
        }
        vector <int> tungtung;
        if(tes==4)if(backt.size()<2)continue;

        bool lampar=0;

        vector <int> usink;
        vector <int> usink2;
        ll mee=INF;
        usink.push_back(w.Y);
        usink2.push_back(w.X);
        int brg=1;
        for(int i=0;i<backt.size();i++)
        {
            int c=backt[i];
            bool lam=0;
            for(auto brbrrpat:nope[c])
            {
                if(brbrrpat==w.X)continue;
                if(usink.size()>=4)break;
                if(used[brbrrpat]==0)
                {
                    lam=1;
                    usink2.push_back(brbrrpat);
                    usink.push_back(c);
                }
            }
            if(lam&&c!=w.Y)brg++;
            if(lam==0)
            {
                break;
            }
            if(usink.size()>=4)break;

        }
        if(tes==4&&usink.size()<4)continue;
        if(tes==3&&usink.size()<3)continue;
        if(tes==2&&usink.size()<2)continue;
        int momenta;
        if(lampar)continue;
        ll costN=INF;
        bool lampi=0;
        int ele=0;
        for(auto c:usink)
        {
            ab[c]=INF;
            for(int i=1;i<=2000;i++)
            {
                if(moment[i]==0)
                {
                    ab[c]=min(cost[c][i],ab[c]);
                }
            }
        }

        for(int i=1;i<=2000;i++)
        {
            if(moment[i]==0)
            {
                ll sum=costN-1;
                int be=0;
                if(brg==2)be=0;
                else if(brg==3)be=0;
                if(brg==4)be=0;
                if(usink.size()==4){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be&&cost[usink[3]][i]<=ab[usink[3]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=4;
                }}
                if(usink.size()>=3){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be&&cost[usink[2]][i]<=ab[usink[2]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=3;
                }}
                if(usink.size()>=2){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be&&cost[usink[1]][i]<=ab[usink[1]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=2;
                }}
                if(usink.size()>=1){
                if(sum<costN&&cost[usink[0]][i]<=ab[usink[0]]+be)
                {
                    lampi=1;
                    costN=sum;
                    momenta=i;
                    ele=1;
                }}
            }
        }

        if(lampi==0)continue;
        int br=0;
        for(auto c:usink2)
        {
            br++;
            if(br>ele)break;
            nk.push_back(c);
        }
        reverse(backt.begin(),backt.end());
        moment[momenta]=1;
        okk=momenta;
        vector <int> nik;
        //cout<<okk<<" "<<)<<" "<<<<endl;
        nik.push_back(okk);
        nik.push_back(nk.size());
        nik.push_back(backt.size());
        ha++;
        for(auto gi:nk)
        {
            //if(used[gi]==1)lampat=1;
            nik.push_back(gi);
            used[gi]=1;
        }
        for(auto c:backt)
        {
            nik.push_back(c);
        }
        //nik.push_back(d[w.Y]);
        ans.push_back(nik);
    }}




    bool lampichka=0;
    cout<<ha<<endl;
    int brr=0;
    int sz1=0,sz2=0;
    bool lampa=1;
    sort(ans.begin(),ans.end(),comp);
    for(auto w:ans)
    {
        for(auto c:w)
        {
            cout<<c<<" ";
        }ENTER;
    }
}

int main()
{
    #ifdef ONLINE_JUDGE
    freopen("transport.in", "r", stdin);
    freopen("transport.out", "w", stdout);
    #endif
    speed();
    solve();
    return 0;
}