#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>

using namespace std;

vector<vector<pair<int,int>>> G;

void print(const vector<vector<pair<int,int>>>& G)
{
    int index = 0;
    for (auto i = G.begin(); i != G.end(); i++, index++)
    {
        cout << index << ": ";
        for (auto j: (*i))
        {
            cout << j.first << "(" << j.second << ") ";
        }
        cout << endl;
    }
}

vector<double> Dijkstra(vector<vector<pair<int,int>>>& G, int s)
{
    vector<double> d;
    d.assign(G.size(),INFINITY);
    d[s]=0;

    vector<int> T;
    for (int i = 0; i < G.size(); i++)
        T.push_back(i); // T = {0,1,2,...,n-1}
    while (T.size()!=0)
    {
        int w = *(T.begin());
        for (auto i : T)
            if (d[i]<d[w])
                w = i;
        for (auto i = T.begin(); i != T.end(); i++)
            if ((*i) == w)
            {
                T.erase(i);
                break;
            }


        for (auto v : T)
        {
            double weight = INFINITY;
            for (auto i : G[w])
                if (i.first == v)
                {
                    weight = i.second;
                    break;
                }
            if (d[v] > d[w] + weight)
                d[v] = d[w] + weight;
        }
    }
    return d;
}

int main()
{
    srand(time(nullptr));
    //ifstream in(?);
    int n = 8;
    //in >> n;
    for (int i = 0; i < n; i++)
    {
        G.push_back(vector<pair<int,int>>());
        int m = rand()%n;
        //in >> m;
        for (int j = 0; j < m; j++)
        {
            int t1 = rand()%n, t2 = rand()%20;
            //in >> t1 >> t2;
            G[i].push_back(make_pair(t1,t2));
        }
    }

    print(G);

    vector<double> res = Dijkstra(G,0);

    cout << endl << endl;
    for (auto i : res)
    {
        cout << i << endl;
    }
    return 0;
}