const int N = 1e5 + 10;
int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1;i <= n; i++)
{ 
    sum[i] = sum[i - 1] + a[i];   
}

s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i] [j] - s[i - 1][j - 1]

matrixSum(int x1,int y1,int x2,int y2){}
return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}
// 求（x1,y1）[含]~（x2，y2）[含]的和。注意这里有-1！

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
	// 注意这里是往后看+1！！！
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    // 注意这里从1开始，无妨
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            insert(i, j, i, j, a[i][j]);      //构建差分数组,可以类似于插入元数据
        }
    }
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);// 修改
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二维前缀和
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}
 

void solve()
{
	int res=n+1;
	int s=0,t=0,sum=0;
	//初始化起点和终点
	for(;;)
	{
		while(t<n&&sum<S)
		// 当右指针未到尾部，且综合小于S
		{
			sum+=a[t++];
			// 累加 右指针向后移动
		}
		if(sum<S)	
			break;// 这一段标识t>=n了，所以该推出循环了
		res=min(res,t-s);// 取长度最小的
		sum-=a[s++];// 左指针移动
	 } 
	 if(res>n)
	 	res=0;
	cout<<res;
}

int add_dandian(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]+=k;
}

int ask(x){
	int sum = 0;
	for(int i=x;i;i-=lowbit(i)){
		sum+=t[i];
	}
	return sum;
}

int search(int L,int R)
{
	int ans = 0;
	for(int i=L-1;i;i-=lowbit(i))
		ans-=t[i];
	for(int i=R;i;i-=lowbit(i))
		ans+=t[i];
	return 0;
}

ll ask(int pos)//返回区间pos到1的总和
{
	ll ans=0;
	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];
	return ans;
} 

// 建立线段树
int a[n];
int sum[n*4];
void push(int o)
{
// 核心，在push的时候就算一下
    sum[o]=sum[o*2]+sum[o*2+1];// 
}
// l、r、o都是下标喵
void build(int l,int r,int o)
{
    if(l==r)
    {
        sum[o]=a[l];
    }
    else
    {
        int mid=(l+r)/2;
        build(l,mid,o*2);
        build(mid+1,r,o*2+1);
        push(o);
    }
}

// 修改树
void updata(int p,int l,int r,int o,int k)//要修改的点，左边界，有边界，节点，有修改的值
{
    if(l==r)
    {
        a[o]+=k;//修改点
        sum[o]+=k;//修改和
    }
    else
    {
        int mid=(l+r)/2;// 看到底是左子树改了还是右子树改了
        if(p<=mid)
        {
            updata(p,l,mid,o*2,k);//递归修改左子树
        }
        else
        {
            updata(p,mid+1,r,o*2+1,k);//右子树
        }
        push(o);//老朋友，别说不认识
    }
}

void down(int l,int r,int o)
{
    if(tag[o])//如果该节点没有打上tag，那也就没有必要去传递了（你也不希望你的程序会跑个寂寞吧）
    {
        int mid=(l+r)/2;
        tag[o*2]+=tag[o];//下传给左子树
        tag[o*2+1]+=tag[o];//下传给右子树
        sum[o*2]+=tag[o]*(mid-l+1);//修改左子树和，因为该节点下面有（mid-l+1)个节点，每个节点+k；
        sum[o*2+1]+=tag[o]*(r-mid);//修改右子树和，因为该节点下面有（r-mid)个节点，每个节点+k；
        tag[o]=0;//该节点的tag值已传给子节点，自己可以先退役了（忘了你试逝）
    }
}
// 假设是怼(l,r)这一组每个结点都要全部加上k。
void updata(int L,int R,int l,int r,int o,int k)//查询区间的左边界、右边界，线段树的左边界、右边界，节点，要加的值
{
    if(l>=L&&r<=R)//当修改区间完全覆盖查找到的区间，把查找到的区间的和修改，并修改该节点的tag值
    {
        tag[o]+=k;          //修改点，比如修改是加上k（）
        sum[o]+=k*（r-l+1）;//修改和，【因为该节点下面有（r-l+1)个节点】，每个节点+k；
    }
    else
    {
        down(l,r,o);//下传标记 //！
        int mid=(l+r)/2;
        if(L<=mid)
        {
            updata(L,R,l,mid,o*2,k);//递归左子树
        }
        if(mid<R)
        {
            updata(L,R,mid+1,r,o*2+1,k);//右子树
        }
        push(o);//老朋友，别说不认识
    }
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hashmap;
        stack<int> st;// 栈
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];//从后向前遍历
            // 不断访问栈顶，如果栈顶更大，那么直接弹出来
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            // 这个num的下一个最大的元素即是栈顶，如果栈为空，那么就是-1
            hashmap[num] = st.empty() ? -1 : st.top();
            // 把这个元素也压入栈
            st.push(num);
        }
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};

class Solution {
public:
    int shortestSubarray(vector<int> &nums, int k) {
        int n = nums.size(), ans = n + 1;
        long s[n + 1];
        s[0] = 0L;
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] + nums[i]; // 计算前缀和
        deque<int> q;
        for (int i = 0; i <= n; ++i) {
            long cur_s = s[i];
            while (!q.empty() && cur_s - s[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front(); // 优化一
            }
            while (!q.empty() && s[q.back()] >= cur_s)
                q.pop_back(); // 优化二
            q.push_back(i);
        }
        return ans > n ? -1 : ans;
    }
};

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int len = nums.size();
        int ans = 0;

        stack<int> s;

        for (int i = 0; i < len; i++) {
            if (s.empty() || nums[s.top()] > nums[i]) {
                s.push(i); // 感兴趣的i。保持严格递减。
            }
        }
        int res = 0;
        for (int j = len - 1; j >= 0; j--) {
            while (!s.empty() && nums[s.top()] <= nums[j]) {
                int pos = s.top();
                s.pop();
                res = max(res, j - pos);
            }
        }
        return res;
    }
};

class Solution {
public:
    int longestWPI(vector<int> &hours) {
        int n = hours.size(), ans = 0, s[n + 1]; // 前缀和
        stack<int> st;
        st.push(s[0] = 0);
        for (int j = 1; j <= n; ++j) {
            s[j] = s[j - 1] + (hours[j - 1] > 8 ? 1 : -1);
            if (s[j] < s[st.top()]) st.push(j); // 感兴趣的 j
        }
        for (int i = n; i; --i)
            while (!st.empty() && s[i] > s[st.top()]) {
                ans = max(ans, i - st.top()); // [栈顶,i) 可能是最长子数组
                st.pop();
            }
        return ans;
    }
};

// 伪代码
	int M = pat.length();// 需要匹配的字符串
    int N = txt.length();
    // pat 的初始态为 0
    int j = 0;
    for (int i = 0; i < N; i++) {
        // 当前是状态 j，遇到字符 txt[i]，
        // pat 应该转移到哪个状态？
        j = dp[j][txt.charAt(i)];
        // 如果达到终止态，返回匹配开头的索引
        if (j == M) return i - M + 1;
    }
    // 没到达终止态，匹配失败
    return -1;

public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        // 状态即当前匹配到字符下标（还没匹配），字符就是这个字符是什么
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0: 只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，遇到其它字符的话还是停留在状态 0
        int X = 0;
        // 当前状态 j 从 1 开始
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
            // 遍历不同的情况
                if (pat.charAt(j) == c) 
                    dp[j][c] = j + 1;// 推进
                else 
                    dp[j][c] = dp[X][c];// 返回：找到公共前缀的位置
            }
            // 更新影子状态（公共前缀的位置），参考动图*********
            X = dp[X][pat.charAt(j)];// 当前匹配到X下标，这个字符是j需要转移的位置
        }

vector<int> commpute_next(string pattern){
// next数组就是转移，代表遇到i不匹配的时候，前面前缀和匹配了多少
    vector<int>next(pattern.size() + 1, 0);
    next[0] = -1;// 0，我们按下标从1开始即next(1)表示匹配了一个字符后，转移到的pattern的下标
    for (int i = 2; i < next.size(); ++i) {
    // 从2开始，因为1为0，即第一个匹配错误，指针还是在0
        for (int j = 1; j < i; ++j) {
            if (pattern.substr(0, j) == pattern.substr(i - j, j)) {
            // 如果从0开始的j位前缀=从i-j位开始的j位，那么可以认为当前下标为j
            // 比如 abcdabd，我们发现ab有重复，也就是如果待匹配串为abcdabcdabd时，ab已经匹配过了，前缀公共为2，所以j=2
                next[i] = j;
            }
        }
    }
    return next;
}
int kmp(string str,string pattern){
    vector<int> next = commpute_next(pattern);
    int i = 0;
    int j = 0;
    while (i < str.size()) {
        if (str[i] != pattern[j]) {
            j = next[j];// 不等于就回退到公共前缀位置
            if (j == -1) { //表示当前没有已匹配字符
                i++; //寻找下一个匹配的pattern首字母
                j = 0; //指针移到pattern开头
            }
        }else{
            i++;
            j++;
            if (j == pattern.size()) {
            // 匹配成功
                return (int) (i - pattern.size());
            }
        }
    }
    return -1;
}

  vector<int> commpute_next(string pattern){
        vector<int>next(pattern.size() + 1, 0);
        next[0] = -1;
        next[1] = 0; // 长度为1的字符串没有前后缀
        int i = 2; // i表示next数组的索引
        int k = 0; // 指针指向pattern的位置
        while (i < next.size()) {
		    // 如果当前字符匹配成功
            if (pattern[i - 1] == pattern[k]) {
            // pattern索引比next索引小1，因为next从1开始。
	    

				// 匹配上了，同时+1
                next[i] = k + 1;
                k = next[i];
                ++i;
		    // 如果指针已经指向pattern[0]却还没有匹配成功
            } else if (k == 0){
                next[i] = 0;
                ++i;
            } else{
                k = next[k]; //可以利用已匹配成功的信息，让指针不进行回退，查找next数组
            }
        }
        return next;
    }

int kmp(string str,string pattern){
        vector<int> next = commpute_next(pattern);
        int i = 0;
        int j = 0;
        while (i < str.size()) {
            if (str[i] != pattern[j]) {
                j = next[j];
                if (j == -1) { //表示当前没有已匹配字符
                    i++; //寻找下一个匹配的pattern首字母
                    j = 0; //指针移到pattern开头
                }
            }else{
                i++;
                j++;
                if (j == pattern.size()) {
                    return (int) (i - pattern.size()); 
                }
            }
        }
        return -1;
    }

#include <bits/stdc++.h>
using namespace std;
const int N = 8e5+5;
int s[N];
void init_set(){                  //初始化
   for(int i=1; i<=N; i++)  s[i] = i;
}
int find_set(int x){               //查找
  //if (x==s[x]) return x;
  //else return find_set(s[x]);   //这2行合并为下面的1行
    return x==s[x]? x:find_set(s[x]);
}
void merge_set(int x, int y){    //合并
    x = find_set(x);
    y = find_set(y);
    if(x != y) s[x] = s[y];      //y成为x的父亲，x的集是y
}
int main (){
    init_set();
    int n,m; cin>>n>>m;
    while(m--){
        int op,x,y; cin>>op>>x>>y;
        if(op == 1)   merge_set(x, y);
        if(op == 2){
            if(find_set(x)==find_set(y)) cout << "YES"<<endl;
            else                         cout << "NO"<<endl;
        }
    }
    return 0;
}

int find_set(int x){
    if(x != s[x])   
	    s[x] = find_set(s[x]);   //路径压缩，直接找根结点
    return s[x];
}

#include <bits/stdc++.h>
using namespace std;
const int N = 8e5+5;
int s[N];
void init_set(){                  //初始化
   for(int i=0; i<N; i++)  
	   s[i] = i;
}
int find_set(int x){
    if(x != s[x])   
	    s[x] = find_set(s[x]);   //路径压缩，即在返回查找时候顺便更改至根结点（原来只是判递归而已）
    return s[x];
}
void merge_set(int x, int y){    //合并
    x = find_set(x);// 这里要注意 x变成了传入x的集合编号
    y = find_set(y);// 这里要注意 y变成了传入y的集合编号
    if(x != y) 
	    s[x] = s[y];      //y成为x的父亲，x的集是y
}
int main (){
    init_set();
    int n,m; cin>>n>>m;
    while(m--){
        int op,x,y; cin>>op>>x>>y;
        if(op == 1)   merge_set(x, y);
        if(op == 2){
            if(find_set(x)==find_set(y)) cout << "YES"<<endl;
            else                         cout << "NO"<<endl;
        }
    }
    return 0;
}

unordered_set<int> Sets;
    for (int i = 1; i <= PlantNum; i++)
    {
        Sets.insert(find_set(i));
    }
    cout << Sets.size() << endl;

void init_set()
{
    for (int i = 1; i <= N; i++)
    {
        myset[i] = i;
        setSum[i] = 1; // 只有一个人
    }
    return;
}

void merge_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if (x != y)
    {
        myset[x] = myset[y];
        int numX = setSum[x];
        int numY = setSum[y];
        setSum[x] += numY; // 增加集合内元素个数
        setSum[y] += numX; // 增加集合内元素个数
    }
    return;
}

#include<bits/stdc++.h>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
const int N=2e5+5;

int n,m;
ll ans;
struct edge{
	int u,v,w;
}e[N];
int f[5005],add=1;

bool cmp(edge a,edge b){return a.w<b.w;}

/*熟悉的查并集代码*/
inline int find(int k)
{
	if(f[k]==k)
		return k;
	else 
		return f[k]=find(f[k]);
}

inline void link(int a,int b)
{
	f[find(b)]=find(a);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	for(int i=0;i<5005;i++)f[i]=i;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		e[i]=(edge){a,b,c};
	}
	sort(e,e+m,cmp);// e从小到大排列
	for(int i=0;i<m&&add<=n;i++){
	// 加入m条边，加入的结点，注意，最开始的add=1（初始化，即最小的结点），所以需要加到n才可以
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
		// 如果祖先一样，则跳过，因为祖先一样不必加入这个边
			link(u,v);// 链接，并集
			ans+=w;
			add++;
		}
	}
	if(add!=n)cout<<"orz";//不连通 
	else cout<<ans;
	return 0;
}

//fa表示每个点的父节点，deep表示每个点的深度 
int fa[100],deep[100];
int LCA(int a,int b)
{
	//在函数中确保a的深度大于b的深度，方便后面操作。 
	if(deep[a]<deep[b])
		swap(a,b);
	//让b不断地跳到他的父节点上，直到与a的深度相同 
	while(deep[a]>deep[b])
		b=deep[b];
	//让a和b同时往上跳，直到两者相遇。 
	while(a!=b)
	{
		a=deep[a];
		b=deep[b];
	}
	return a;
}

//fa表示每个点的父节点 
int fa[100],DP[100][20];
void init()
{
	//n为结点数，先初始化DP数组 
	for(int i=1;i<=n;i++)
		dp[i][0]=fa[i];
	//动态规划求出整个DP数组 
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)
			DP[i][j]=DP[DP[i][j-1]][j-1];
}

//查询函数
int LCA(int a,int b)
{
    //确保a的深度大于b，便于后面操作。
	if(dep[a]<dep[b])
		swap(a,b);
    //让a不断往上跳，直到与b处于同一深度
    //若不能确保a的深度大于b，则在这一步中就无法确定往上跳的是a还是b

	
	for(int i=19;i>=0;i--)
	{
        //往上跳就是深度减少的过程
		if(dep[a]-(1<<i)>=dep[b])
		// 【第1次回溯】a的深度如果还深于B 可以
			a=dp[a][i];
	}
	// for循环结束后，两者必定处于同一深度
	
    //若二者处于同一深度后，正好相遇，则这个点就是LCA
	if(a==b)
		return a;
	
    //【第二次回溯】a和b同时往上跳，从大到小遍历步长，遇到合适的就跳上去，不合适就减少步长
	for(int i=19;i>=0;i--)
	{
        //若二者没相遇则跳上去
		if(dp[a][i]!=dp[b][i])
		{
			a=dp[a][i];
			b=dp[b][i];
		}
	}
    //最后a和b跳到了LCA的下一层，LCA就是a和b的父节点
	return dp[a][0];
}

struct node
{
	int to;
	int next;
}edge[maxn];

struct node
{
	int to;
	int next;
}edge[maxn];
int head[maxn];
int cnt=1;//表示edge数组的下标，也可以表示已经存入的边数
void add(int from,int t)
{
	edge[cnt].to=t;// 终点下标
	edge[cnt].next=head[from];// 上一条相同起点边的下标
	head[from]=cnt;// 更新head
	cnt++;
}

#include<iostream>
using namespace std;
const int maxn=1000;
struct node
{
	int to;
	int next;
}edge[maxn];
int head[maxn];
int cnt=1;
void add(int from,int t)
{
	edge[cnt].to=t;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
bool s[maxn];
void dfs(int x)
{
    s[x]=true;
    printf("%d ",x);
    for(int i=head[x];i!=0;i=edge[i].next)
    {
    	if(!s[edge[i].to])
        	dfs(edge[i].to);
    }
}
 
int main()
{
	int u,v,w;
	int n;
	cin>>n;
	while(n--)
	{
		cin>>u>>v;
		add(u,v);
	}
	dfs(1);
	return 0;
}

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int maxn=500005;
//保存图结构 
struct node
{
	int to;
	int next;
}e[2*maxn];
int head[maxn];
int cnt;
void add(int a,int b)
{
	e[++cnt].to=b;
	e[cnt].next=head[a];
	head[a]=cnt;
}
bool vis[maxn];
int main()
{
	int n,u,v;
	cin>>n;
	while(n--)
	{
		cin>>u>>v;
		add(u,v);
	}
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		vis[temp]=true;
		printf("%d ",temp);
		for(int i=head[temp];i;i=e[i].next)
		{
			if(!vis[e[i].to])
				q.push(e[i].to);
		}
	}
    return 0;
}

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn=500005;
int root,n,m,a,b,c;
//保存图结构 
struct node
{
	int to;
	int next;
}e[2*maxn];
int head[maxn];
int cnt;
void add(int a,int b)
{
	e[++cnt].to=b;
	e[cnt].next=head[a];
	head[a]=cnt;
}
 
//遍历图，求出各节点的深度，并求出fa数组 
int fa[maxn][20],dep[maxn];
void dfs(int root,int pre)
{
    dep[root]=dep[pre]+1;// 设置root的为1
    fa[root][0]=pre;// root结点的上一层祖先是pre
    // 设置从根结点上面i（i=2、4、8、16）步的祖结点
    for(int i=1;(1<<i)<=dep[root];i++)
    	fa[root][i]=fa[fa[root][i-1]][i-1];
    // 继续遍历剩余的图
    for(int i=head[root];i;i=e[i].next)
    {
        if(e[i].to!=pre)
        	dfs(e[i].to,root);
    }
}
//查询函数 
int LCA(int a,int b)
{
    if(dep[a]<dep[b])
        swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(dep[a]-(1<<i)>=dep[b])
            a=fa[a][i];
    }
    if(a==b)
        return a;
    for(int i=19;i>=0;i--)
    {
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main()
{
    cin>>n>>m>>root;
    // 建图
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);// 注意是否要建立双向图
        add(b,a);
    }
    dfs(root,0);// 搜索，建立deep数组
    while(m--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",LCA(a,b));
    }
    return 0;
}

// myEgde时一个类似于二维数组的东西，myEgde[now]表示以now为起点的所有终点的集合。
void bfs(vector<unordered_set<int>> &myEgde, int start, int end)
{
    int d[500] = {INT_MAX};    // d数组记录从起始顶点START到各个顶点最短路径
    int path[500] = {-1};      // path数组记录最短路径从哪个顶点过来
    bool visit[500] = {false}; // 访问标记数组

    d[start] = 0; // 初始长度为0
    visit[start] = true;
    deque<int> myDeque;
    myDeque.push_back(start);
    while (!myDeque.empty())
    {
        int now = myDeque.front(); // 队头出队
        myDeque.pop_front();
        for (const auto &next : myEgde[now])
        {
            if (!visit[next])
            {
                d[next] = d[now] + 1;   // 路径长度+1
                path[next] = now;       // 最短路径从顶点now到顶点next，输出最短路径的时候可以倒叙输出即可找到最短路径
                visit[next] = true;     // 标记已访问
                myDeque.push_back(now); // 将顶点w入队
            }
        }
    }
    cout << d[end] << endl;// 输出最短路径长度
    return;
}

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
using ll = long long;
struct Edge {
    int to;
    ll weight;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<Edge>> G(N + 1);
    int i, j, k;
    for (i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({ v, w });
    }
    vector<ll> dist(N + 1, INF);
    dist[1] = 0;// 当前在1点
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;// 小根堆，存储 `(距离, 点)`
    Q.push({ 0, 1 });// 从1到1，权重为0
    while (!Q.empty()) {
        auto [d, u] = Q.top();//获取距离 `d` 和点 `u`。
        Q.pop();
        if (d > dist[u]) continue;// u是原点到目标点的举例。如果堆顶元素的距离大于已知的 `dist[u]`（这意味着在堆中存在一个更短的路径到点 `u`），则跳过当前迭代。
        for (const auto &[v, w] : G[u]) {
        // 遍历与点 `u` 相连的所有边 `[v, w]`，其中 `v` 是相邻点，`w` 是从 `u` 到 `v` 的边的权重。
            if (dist[u] + w < dist[v]) {
            // 如果通过当前边 `[u, v]` 到达点 `v` 的路径比已知的最短路径更短。
                dist[v] = dist[u] + w;
                //更新点 `v` 的最短距离。
                Q.push({ dist[v], v });// 原点到v的距离是dist[v]
            }
        }
    }
    for (j = 1; j <= N; j++) {
        if (dist[j] == INF) cout << "-1" << " ";
        else cout << dist[j] << " ";
    }
    return 0;
}

int spfa()
{
    //初始化所有点的距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //定义一个队列存储所有待更新的点
    queue<int> q;
    //把1号点放到队列里面去
    q.push(1);
    st[1] = true;
    //当堆不为空
    while(heap.size())
    {
        //每次取出来队头
        int t = q.front();
        //删除队头
        q.pop();
        //把st[]置为false表示这个点不在队列里面
        st[t] = false;
        //更新t的所有邻边
        for(int i = h[t]; i != -1; i = ne[i])
        {    
            //用j来表示当前这个点
            int j = e[i];
            //看是否能够更新这个点
            if(dist[j] > dist[t] + w[i])
            {
                //更新
                dist[j] = dist[t] + w[i];
                //只有j不在队列里面才把它加到队列里面去
                // 与DJS的区别在于：一个结点可以多次进入队列中进行更新
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if(dist[n] == ox3f3f3f) return -1;
    return dist[n];

#include <bits/stdc++.h>
using namespace std;
long long INF = 0x3f3f3f3f3f3f3f3f; // 定义无穷大变量
int n, m, t;
long long dp[500][500]; // 存储最短路

void input()
{ // 输入函数
    int x, y;
    long long z;
    scanf("%d %d %d", &n, &m, &t);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %lld", &x, &y, &z);
        // x到y和y到x是一样的路径
        dp[x][y] = dp[y][x] = min(dp[x][y], z); // 防止路径重复，选取最小权重
    }
}

void Floyd()
{ // 最短路径函数（Floyd算法）
    for (int k = 1; k <= n; k++)
    // 注意！！！K在最外层！！！！！！！！
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                // 挑选中间的一个k，看看有没有中转更小的
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }
}

void ouput()
{ // 输出函数
    int v, u;
    while (t--)
    {
        scanf("%d %d", &v, &u);
        if (dp[v][u] == INF)
            printf("-1\n");
        else if (v == u)
            printf("0\n");
        else
            printf("%lld\n", dp[v][u]);
    }
}

int main()
{
    for (int i = 0; i <= 500; i++)
    { // 初始化为无穷大
        for (int k = 0; k <= 500; k++)
            dp[i][k] = INF;
    }
    input();
    Floyd();
    ouput();
    return 0;
}

class Solution {
public:  
    vector<vector<int>> edgs;
    vector<int> dfn;
    vector<int> low;
    vector<bool> visit;
    vector<vector<int>> ret;
    int times;
    
    void tarjan(int node, int parent){
        times++;
        dfn[node] = times;
        low[node] = times;
        visit[node] = true;
    
        for (auto e : edgs[node]){
        // e是目的地
            if (e == parent) continue;
            // 如果是父节点就不管了（反向边），即看了5->7,7又回来找5
            if (!visit[e]){
                tarjan(e, node);
                low[node] = min(low[e], low[node]);// 同一个环，统一一个代码


                // 核心代码：在一张无向图中，判断边 e （其对应的两个节点分别为 u 与 v）是否为桥，需要其满足如下条件即可：dfn[u] < low[v]。最小到达目的地时间都大于当前时间
                if(low[e] > dfn[node]){
                    ret.push_back({node, e});
                } 
            }else{
                low[node] = min(low[node], dfn[e]);
            }
                
        }
    }
    
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        dfn = vector<int>(n,0);
        low = vector<int>(n,0);
        visit = vector<bool>(n,false);
        edgs = vector<vector<int>>(n);
        times = 0;
        
        for(auto & conn : connections){
            edgs[conn[0]].push_back(conn[1]);
            edgs[conn[1]].push_back(conn[0]);
        }
        
        tarjan(0,0);// 最开始的是本身
        return ret;
    }
};

for (int i=1;i<=n;i++)
        if (DFN[i]==0)
            tarjan (i,i);
            // 注意，若图不一定联通，则要遍历每个点，我们让最开始的点的父节点为本身
//fa代表父亲节点
// 最开始是本身
void tarjan (int u, int fa) {
    dfn[u] = low[u] = ++id; //id代表时间戳
    int child = 0; //child代表子树数目, 只有u是根节点时, 这个变量才会起作用哟
    for (int i = head[u]; i; i = e[i].nxt) {    //链式前向星的遍历操作
        int to = e[i].to;
        if (!dfn[to]) {
            //如果顶点to没有访问过, 那么继续dfs
            tarjan(to, fa);     //传入当前节点以及父节点作为参数
            low[u] = min(low[u], low[to]);  //回溯的时候更新low数组的值
            /*相比桥核心修改*/
            if (low[to]>=DFN[u]&&u!=fa)
            // 注意这里取等也可以哦！不取等就是桥（桥的另一边用取等号来添加），肯定是割点。
                cut[u]=1;
            if(u==fa)// 这增加了对父结点就是本身的特判
                child++;
                /*
                1 -> 2
				|    |
				v    v
				3    4
				如果以1为起点，其实1也是割点！
                */
            /*相比桥核心修改*/
        }
		else{
	        low[u] = min(low[u], dfn[to]);  //这里的更新操作不要漏掉了
        }
        /*相比桥核心修改*/
        if (child>=2&&u==fa)
	        cut[u]=1;
	    /*相比桥核心修改*/
    }
}

for (int i = 1; i <= n; i++) {
    if (cut[i]) {
        ans++;
    }
}
// ans即割点数量

void Tarjan(int u){
	cnt++;// 时刻
	dfn[u]=low[u]=cnt;//初始化dfn=low，当前时刻
	S.push(u);//顶点u入栈
	visit[u]=1;
	for(int i=head[u];i;i=last[i]){//遍历u的所有边
		int v=to[i];//v是以u为起点的边的终点顶点
		if(!dfn[v]){//如果还没有访问过v，注意，这里是通过有没有dfn[v]判断，而不是visit
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(visit[i]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	/*核心增加代码*/
	// 最终如果dfn[u]==low[u]，那么这就是这个编号
	if(dfn[u]==low[u]){
		color[u]=++sum;//颜色+1，用相同的颜色对同一个连通分量染色
		// sum代表联通分量
		visit[u]=0;//标记为未访问
		while(S.top()!=u){
			color[S.top()]=color[u];
			visit[S.top()]=0;//标记为未访问
			S.pop();
		}
		
	}
}

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int,vector<int>> edges;
        vector<int> in(numCourses,0);// 注意，他的边的定义是[3,4]，3<-4

        for(vector<int>& e:prerequisites){
            int a=e[0],b=e[1];
            edges[b].push_back(a);
            in[a]++;// 入度
        }

        queue<int> q;
        vector<int> ret;
        for(int i=0;i<numCourses;++i) 
            if(in[i]==0){
                q.push(i);
                ret.push_back(i);
            } 

        while(!q.empty()){
            int t=q.front();// 取队头结点
            q.pop();
            for(int e:edges[t]){
                in[e]--;// 对头相连接的结点入读--
                if(in[e]==0){ 
                    q.push(e);
                    ret.push_back(e);    
                }
            }
        }

        for(int i:in) if(i) return {};// 检查是否所有入度都是0
        return ret;
    }
};