using namespace std;
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <queue>
#include <bitset>
#define maxn 1001
#define oo 0x3f3f3f3f
#define pb push_back

struct nod { int n;int c;nod(){}; nod(int a, int b){n=a; c=b;};};

vector<nod>a[maxn];



int D[maxn][maxn];
bool use[maxn];
int st[maxn], nst;
int n, Q, R;



void read()
{
	int p, q, c, m;
	
	//freopen("conflicte.in","r",stdin);
	scanf("%d %d %d\n", &n, &m, &Q);
	//printf("%d %d %d\n",n, m, Q);
	while(m--)
	{
		scanf("%d %d %d\n", &p, &q, &c);
		a[q].pb(nod(p, c));
	}
	
	
}





inline void dfs(int n)
{
	vector<nod>::iterator it;
	use[n]=1;
	
	for(it=a[n].begin();it!=a[n].end();++it)
		if(!use[it->n]) dfs(it->n);
	
	st[++nst]=n;
}

inline int memo(int i, int j)
{
	//printf("%d %d\n", i, j);
	if(D[i][j]!=-1) return D[i][j];
	if(i==j) return 0;

	vector<nod>::iterator it;
	
	int s=oo;
	for(it=a[i].begin();it!=a[i].end();++it)
		s=min(s, memo(it->n, j)+it->c);
	
	for(it=a[j].begin();it!=a[j].end();++it)
		s=min(s, memo(i, it->n)+it->c);
	//if(s==oo) s=-1;
	D[i][j]=s;
	return s;
}



inline int min(int a, int b)
{
	if(a<b) return a;
	return b;
}


void solve()
{
	int p=1, q=2,s, i, ok;
	 int t;
	++Q;
//	printf("%d\n", Q);
	while(--Q)
	{
		scanf("%d %d\n", &p, &q);

		//p	rintf("%d %d\n", p, q);
		t=D[p][q];
		if(t==oo) t=-1;
		printf("%d\n",t);
		
		
	}
	
}

int main()
{
//	freopen("conflicte.out","w",stdout);
	/*
	read();
	//getdistances();
	//dijkstra();
//	warshal();
	memset(D, -1, sizeof(D));
int i, j, k;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			memo(i, j);
	//for(i=1;i<=n;++i) D[i][i]=0;
		solve();	
//	for(int i=1;i<=n;++i)
//		for(int j=1;j<=n;++j) if(x[i][j]) printf("%d %d\n", i, j);
	
*/

	int i, j,k;
	n=1000;
	int T=5000;
	for(i=1;i<=T;++i)	
		for(j=1;j<=T;++j) k=min(D[i%n][j%n], k);
	

	return 0;
}