ALGO Short

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

namespace Mlxa {
    typedef long long ll;
    const ll INF(1e17);
    #define read cin
    #define eol '\n'
    #define endln cout << eol
    #define print(a) cout << a << ' '

    template <class T> inline void
    println (T t) { cout << t << eol; }
    template <class A, class... B> inline void
    println (A a, B... b) { print(a); println(b...); }

    #define size(a) ll(a.size())
    #define all(a) begin(a), end(a)
    #define pb push_back
    #define mp make_pair
    #define vec vector
} using namespace Mlxa;

/* vertex from 1 to n!!! */
vec <vec<ll> > Floyd (vec< vec<ll> > &C, ll n) {
    vec< vec<ll> > p(n+1, vec<ll>(n+1, 0));
    for (ll k(1); k <= n; ++ k)
        for (ll i(1); i <= n; ++ i)
            for (ll j(1); j <= n; ++ j)
            if (C[i][k] < INF && C[k][j] < INF)
            if (C[i][j] > C[i][k] + C[k][j])
                C[i][j] = C[i][k] + C[k][j],
                p[i][j] = k;
    return p;
}

vec<ll> dist;
struct cmpp { bool operator () (ll i, ll j) { return dist[i] > dist[j]; } };

vec<ll> Dijkstra (ll start, const vec< vec<ll> > &C, ll n) {
    dist.resize(n+1); fill(all(dist), +INF); dist[start] = 0;
    vec<ll> p(n+1, 0);
    vec<ll> emp;
    priority_queue<ll, vector<ll>, cmpp> near;
    near.push(start);
    while (! near.empty() ) {
        ll v = near.top(); near.pop();
        for (ll u(1); u <= n; ++ u)
        if (dist[u] > dist[v] + C[v][u])
            dist[u] = dist[v] + C[v][u], p[u] = v;
    }
    return p;
}

int main () {
    return 0;
}