int s = 0;
        const int INF = 1000000000;
    vector<long long> d (n+1, INF);
        vector<int> p (n+1);
        vector<bool> visited(n+1, false);
    d[s] = 0;
    priority_queue < pair<int,int> > q;
    q.push (make_pair (0, s));
    while (!q.empty()) {
        int v = q.top().second,  cur_d = -q.top().first;
            visited[v] = true;
        q.pop();
        if (cur_d > d[v])  continue;
        for (size_t j=0; j<graph[v].size(); ++j) {
            int to = graph[v][j].first;
                    if (visited[to] != true) {
                        visited[to] = true;
                        int len = graph[v][j].second;
                        if (d[v] + len < d[to]) {
                                d[to] = d[v] + len;
                                p[to] = v;
                                q.push (make_pair (-d[to], to));
                        }
            }
        }
    }