#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn = 2000 + 10;
const int maxm = 100000 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w, nx;
} e[maxm];
struct Node {
int u, w, t;
bool operator < (const Node& rhs) const {
return w > rhs.w;
}
};
int head[maxn];
int dis[maxn][20];
int total;
bool vis[maxn][20];
void init() {
total = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w) {
e[total].w = w;
e[total].to = v;
e[total].nx = head[u];
head[u] = total++;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
init();
int d;
scanf("%d", &d);
int u, v, w, n = 0;
while (~scanf("%d", &u) && ~u) {
scanf("%d%d", &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
n = std::max({n, u, v});
}
int x, y;
while (~scanf("%d", &x) && x != -2) {
scanf("%d", &y);
std::priority_queue<Node> q;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x][0] = 0;
q.push(Node{x, 0, 0});
while (!q.empty()) {
Node tmp = q.top();
q.pop();
int u = tmp.u, w = tmp.w, t = tmp.t;
if (vis[u][t]) {
continue;
}
vis[u][t] = true;
for (int i = head[u]; ~i; i = e[i].nx) {
v = e[i].to;
if (dis[v][t] > dis[u][t] + e[i].w) { // 不用半价券
dis[v][t] = dis[u][t] + e[i].w;
q.push(Node{v, dis[v][t], t});
}
if (t < d && dis[v][t + 1] > dis[u][t] + (e[i].w >> 1)) { // 用半价券
dis[v][t + 1] = dis[u][t] + (e[i].w >> 1);
q.push(Node{v, dis[v][t + 1], t + 1});
}
}
}
int ans = INF;
for (int i = 0; i <= d; ++i) {
ans = min(ans, dis[y][i]);
}
printf("%d\n", ans);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn = 2000 + 10;
const int maxm = 100000 + 10;
const int INF = 0x3f3f3f3f;
int dis[maxn][20], a[maxn][maxn];
int total;
bool vis[maxn][20];
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
memset(a, 0x3f, sizeof(a));
int d;
scanf("%d", &d);
int u, v, w, n = 0;
while (~scanf("%d", &u) && ~u) {
scanf("%d%d", &v, &w);
a[u][v] = a[v][u] = w;
n = std::max({n, u, v});
}
int x, y;
while (~scanf("%d", &x) && x != -2) {
scanf("%d", &y);
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[x][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int t = 0; t <= d; ++t) {
int _min = INF, u = 0;
for (int j = 0; j <= n; ++j) {
if (!vis[j][t] && _min > dis[j][t]) {
_min = dis[j][t];
u = j;
}
}
if (_min >= INF) {
break;
}
vis[u][t] = true;
for (int v = 0; v <= n; ++v) {
if (dis[v][t] > dis[u][t] + a[u][v]) {
dis[v][t] = dis[u][t] + a[u][v];
}
if (t < d && dis[v][t + 1] > dis[u][t] + (a[u][v] >> 1)) {
dis[v][t + 1] = dis[u][t] + (a[u][v] >> 1);
}
}
}
}
int ans = INF;
for (int i = 0; i <= d; ++i) {
ans = min(ans, dis[y][i]);
}
printf("%d\n", ans);
}
return 0;
}