#include <fstream>
#include <vector>
#include <queue>
#define N 2010
#define K2 33000
#define PI pair<int,int>
#define nod first
#define cost second

using namespace std;

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

vector<PI> A[N];
int n,i,j,S[N],k,m,a,b,c,D[N][K2];

int main ()
{
    for (i=1;i<=2000;i++)
        for (j=1;j<K2;j++)
            D[i][j]=999999;
}