#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>

#define MAXN 50010

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct Vecin {
    int y, cost;

    bool operator<(const Vecin& other) const {
        if (cost != other.cost)
            return cost < other.cost;
        return y < other.y
    }
};

int n,m;
int d[MAXN];
vector<Vecin> graf[MAXN];
set<Vecin> q;

void read(){}

void solve ()
{
    for (int i=2; i<=n; i++)
        d[i]=INT_MAX;
    q.insert({1,0});

    while (!q.empty())
    {
        int top = q.begin()->y;
        q.erase(q.begin());

        for (const Vecin& v : graf[top])
        {
            int nc = dmin[top] + v.cost;
            if (dmin[v.y] > nc)
            {
                if(dmin[v.y] != INT_MAX)
                    q.erase({v.y, dmin[v.y});
                dmin[v.y] = nc;
                q.insert({v.y, dmin[v.y});
            }
        }
    }
}

void citire()

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}