void dj()
{
    memset(path, -1, sizeof path);
    priority_queue<PII> q; q.push({0, 1});
    while(q.size())
    {
        PII t = q.top();    q.pop();
        int x = t.x, y = t.y;
        if(path[y] != -1)   continue;
        path[y] = x;
        for(int i = h[y]; i != -1; i = ne[i])
            q.push({x+w[i], e[i]});
    }
}

void add(int a, int b, int c)
{
    e[idx] = b; w[idx] = -c; ne[idx] = h[a]; h[a] = idx ++;
}