#include <iostream>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1005;

struct Edge {
    int b, c;
};

int n, m;

void dijkstra(int s, int dis[], int vis[], vector<Edge> g[], int pre[]) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    dis[s] = 0;
    q.push({ 0, s });
    
    while (!q.empty()) {
        int t = q.top().second;
        vis[t] = 1;
        q.pop();
        for (Edge i : g[t]) {
            if (!vis[i.b] && dis[t] + i.c < dis[i.b]) {
                dis[i.b] = dis...