#include <cstdio>
#include <climits>
#include <algorithm>
#include <ctime>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

void timeStamp( const char *s ) {
	static double start = 0;
	printf("%.2f : %s\n", 1. * (clock() - start) / CLOCKS_PER_SEC, s);
	start = clock();
} 

const int N = 1e6, M = 3e6;

struct Edge {
	int to, w;
};
vector<Edge> c[N];
int d[N];
int qst, qen, q[N];
int cc, in_q[N];

int main() {
	// int max_cc = 0;
	forn(i, N) c[i].clear();
 	forn(i, M) {
		int a = rand() % N;
		int b = rand() % N;
		int w = rand() % 1000;
		c[a].push_back(Edge {b, w});
	}
	timeStamp("gen");

	fill(d, d + N, INT_MAX / 2);
	int start = 0;
	d[start] = 0; 
	auto add_q = [&]( int v ) {
		q[qen++] = v, qen %= N;
		in_q[v] = 1;
	};
	// Левит: "если мы пришли в V по отрицательному ребру, добавь v в начало (т.е. дек)"
	add_q(start);
	while (qst != qen) {
		int v = q[qst++]; qst %= N;
		in_q[v] = 0;
		cc++;
		for (Edge e : c[v])
			if (d[e.to] > d[v] + e.w) {
				d[e.to] = d[v] + e.w;
				if (!in_q[e.to])
					add_q(e.to);
			}

	}
	// for (bool run = 1; run; cc++) {
	// 	run = 0;
	// 	forn(v, N)
	// 		for (Edge e : c[v])
	// 			if (d[e.to] > d[v] + e.w)
	// 				d[e.to] = d[v] + e.w, run = 1;
	// }
	timeStamp("fb");
	printf("cc = %.3f, d = %lld\n", 1. * cc / N, accumulate(d, d + N, 0LL));
}