Untitled

25 100
7
100 5 6
2000 0 1 600
1000 1 3 700
4000 3 4 200
3000 3 1 400
7000 2 1 300
5000 0 2 200
400 2 0 4 850
400 1 0 4 1050
300 1000
400 3 1 4 -1
200 9000 1 3 100
400 3 1 4 150
30
100 10 20
343235942 9 3 730
511588076 3 6 980
103497954 6 0 390
956612808 0 7 960
588911646 7 5 600
33727076 5 4 260
88489754 4 8 490
527630784 8 1 590
106424790 1 2 220
392166108 2 9 330
538766930 2 1 590
837716110 8 7 200
34689228 2 5 920
794963624 0 5 620
929199098 0 9 600
214614198 6 1 680
214206318 0 1 300
749508458 4 5 870
112136364 4 1 610
372776996 0 3 300
400 2 6 3 345
300 538766930
300 837716110
200 592002819 5 6 180
200 288391792 6 5 890
300 112136364
200 812178983 1 4 660
300 749508458
200 815664058 6 9 880
300 88489754
200 608358041 5 0 190
300 34689228
200 368223732 4 9 310
200 418160571 5 2 430
200 61151304 6 7 190
200 769935373 9 4 190
200 25076024 6 3 810
200 724217617 3 0 720
200 742008262 8 5 540
200 979103957 9 0 600
200 654823290 8 3 460
400 4 2 1 615
200 941874617 7 8 300
200 627206534 8 9 150
400 2 6 9 395
200 661152281 1 8 140
200 104380078 2 7 450
200 4877575 7 0 550
400 8 5 4 130
/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

extern void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]);
extern void add(int mId, int sCity, int eCity, int mToll);
extern void remove(int mId);
extern int cost(int M, int sCity, int eCity);

/////////////////////////////////////////////////////////////////////////

#define MAX_K 2000
#define CMD_INIT 100
#define CMD_ADD 200
#define CMD_REMOVE 300
#define CMD_COST 400

static bool run() {
	int q;
	scanf("%d", &q);

	int n, k, m;
	int mIdArr[MAX_K], sCityArr[MAX_K], eCityArr[MAX_K], mTollArr[MAX_K];
	int mId, sCity, eCity, mToll;
	int cmd, ans, ret = 0;
	bool okay = false;

	for (int i = 0; i < q; ++i) {
		scanf("%d", &cmd);
		switch (cmd) {
			case CMD_INIT:
				okay = true;
				scanf("%d %d", &n, &k);
				for (int j = 0; j < k; ++j) {
					scanf("%d %d %d %d", &mIdArr[j], &sCityArr[j], &eCityArr[j], &mTollArr[j]);
				}
				init(n, k, mIdArr, sCityArr, eCityArr, mTollArr);
				break;
			case CMD_ADD:
				scanf("%d %d %d %d", &mId, &sCity, &eCity, &mToll);
				add(mId, sCity, eCity, mToll);
				break;
			case CMD_REMOVE:
				scanf("%d", &mId);
				remove(mId);
				break;
			case CMD_COST:
				scanf("%d %d %d %d", &m, &sCity, &eCity, &ans);
				ret = cost(m, sCity, eCity);
				if (ans != ret)
					okay = false;
				break;
			default:
				okay = false;
				break;
		}
	}
	return okay;
}

int main() {
	setbuf(stdout, NULL);
	freopen("sample_input.txt", "r", stdin);

	int T, MARK;
	scanf("%d %d", &T, &MARK);

	for (int tc = 1; tc <= T; tc++) {
		int score = run() ? MARK : 0;
		printf("#%d %d\n", tc, score);
	}

	return 0;
}
*/
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#define MAX_INT 1e9
using namespace std ;
 
struct EDGE
{
    int id, to , dis ;
    bool isDel ;
    void init(int id , int to , int dis , bool isDel)
    {
        this->id = id ;
        this->to = to ;
        this ->dis = dis ;
        this->isDel = isDel ;
    }
};
// danh sach ke
vector<EDGE> edgePool[305];
unordered_map<int,EDGE> edgeMap ;
 
struct Node
{
    int city ;
    int availVou ;
    int cost ;
    void init(int city ,int avail , int cost)
    {
        this->city = city;
        this->availVou = avail ;
        this->cost = cost ;
    }
};
struct cmp
{
    bool operator ()(const Node &a , const Node &b)
    {
        if (a.cost !=b.cost)
        {
            return a.cost > b.cost ;
        }
        return a.availVou < b.availVou ;
    }
};
// priority_queue
priority_queue<Node,vector<Node>,cmp> pq ;
// thong so ban dau 
int n ,k ;
int minCost[11][305] ;
void add(int mId, int sCity, int eCity, int mToll) {
   EDGE tmpEdge ;
   tmpEdge.init(mId,eCity,mToll,false);
   edgePool[sCity].push_back(tmpEdge);
   edgeMap[mId] = tmpEdge ; 
   return;
} 
 
void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]) {
  
    for (int i = 0; i < n; i++)
    {
        edgePool[i].clear();
    }
    edgeMap.clear();
    n= N ;
    k = K ;
    for (int i = 0; i < k; i++)
    {
        add(mId[i],sCity[i],eCity[i],mToll[i]);
    }
    return;
}
void remove(int mId) {
    edgeMap[mId].isDel = true ;  
}
 
 
int cost(int M, int sCity, int eCity) {
 
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            minCost[j][i] = MAX_INT ;
        }
    }
    // khoi dong
    pq = priority_queue<Node,vector<Node>,cmp> () ;
    Node tmpNode ;
    tmpNode.init(sCity ,M ,0);
    pq.push(tmpNode);
    minCost[1][sCity] = 0 ;
    while (!pq.empty())
    {
        Node curNode = pq.top();
        pq.pop();
 
        // neu den dich
        if (curNode.city == eCity)
        {
            return curNode.cost ;
        }
		if(curNode.cost > minCost[curNode.availVou][curNode.city]) continue;
        // quet
        for (auto i : edgePool[curNode.city])
        {
            if (edgeMap[i.id].isDel == true)
                continue ;
            // khong dung ve 
            int nextCost1 = curNode.cost + i.dis ;
            int nextVou1 = curNode.availVou ;
            if (nextCost1 < minCost[nextVou1][i.to]  )
            {
                minCost[nextVou1][i.to] = nextCost1 ;
                Node tmpNode2 ;
                tmpNode2.init(i.to,nextVou1,nextCost1);
                pq.push(tmpNode2);
            }
            // dung ve 
            if (curNode.availVou >=1 )
            {
                int nextCost2 = curNode.cost + i.dis/2 ;
                int nextVou2 = curNode.availVou - 1;
                if (nextCost2 < minCost[nextVou2][i.to] )
                {
                    minCost[nextVou2][i.to] = nextCost2 ;
                    Node tmpNode3 ;
                    tmpNode3.init(i.to,nextVou2,nextCost2);
                    pq.push(tmpNode3);
                }
            }   
        }
    }
    return -1;
}