#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<climits>

using namespace std;

int const MAXN=51;
int const INF=INT_MAX;

struct Edge{
    int to;
    int len;
    Edge(int x,int y):to(x),len(y){}
};

struct point{
    int num,len;
    point(int x,int y):num(x),len(y){}
    bool operator<(const point& p) const{
        return len>p.len;
    }
};

void Dijistra(vector<Edge> graph[],int dis[]){
    priority_queue<point> mq;
    dis[1]=0;
    mq.push(point(1,dis[0]));
    while(!mq.empty()){
        int u=mq.top().num;
        mq.pop();
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].to;
            int l=graph[u][i].len;
            if(dis[v]>dis[u]+l){
                dis[v]=dis[u]+l;
                mq.push(point(v,dis[v]));
            }
        }
    }
}


int main(){
    int t;
    cin>>t;
    while(t-...