Investigation

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 100001;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int MOD = int(1e9) + 7;
 
vector<pair<ll, int>> edge[MAXN];
ll dist[MAXN];   // distancia mínima
ll num[MAXN];    // número de formas con la distancia mínima
int minf[MAXN];  // vuelos mínimos con distancia mínima
int maxf[MAXN];  // vuelos máximos con distancia mínima
bool v[MAXN];    // si un nodo está visitado
 
void djikstra(int s) {
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
 
	pq.push({dist[s] = 0, s});
	num[s] = 1;
	while (!pq.empty()) {
		int vert = pq.top().second;
		pq.pop();
 
		if (v[vert]) continue;
		v[vert] = true;
		for (auto [cost, next] : edge[vert]) {
			ll alt = cost + dist[vert];
 
			if (alt == dist[next]) {
				num[next] = (num[next] + num[vert]) % MOD;
				minf[next] = min(minf[next], minf[vert] + 1);
				maxf[next] = max(maxf[next], maxf[vert] + 1);
			} else if (alt < dist[next]) {
				num[next] = num[vert];
				minf[next] = minf[vert] + 1;
				maxf[next] = maxf[vert] + 1;
				pq.push({dist[next] = alt, next});
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0, start, end, cost; i < m; i++) {
		cin >> start >> end >> cost;
		edge[start].push_back({cost, end});
	}
	memset(dist + 1, 0x3f, n * sizeof(long long));
	djikstra(1);
	cout << dist[n] << " " << num[n] << " " << minf[n] << " " << maxf[n];
}

import java.io.*;
import java.util.*;
 
public class Investigation {
	static final int MOD = 1000000007;
 
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(in.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		List<List<Pair>> adj = new ArrayList<>(n);
		for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int cost = Integer.parseInt(st.nextToken());
			adj.get(a).add(new Pair(cost, b));
		}
 
		long[] dist = new long[n];
		long[] num = new long[n];
		for (int i = 0; i < n; i++) {
			dist[i] = Long.MAX_VALUE;
			num[i] = 1;
		}
 
		// número máximo de vuelos en la ruta de precio mínimo
		int[] maxf = new int[n];
		// número mínimo de vuelos en la ruta de precio mínimo
		int[] minf = new int[n];
 
		Queue<Pair> toVisit = new PriorityQueue<>();
		// la distancia al nodo de inicio en sí es 0
		dist[0] = 0;
		// f: distancia al nodo actual, s: nodo actual
		toVisit.add(new Pair(0, 0));
		while (!toVisit.isEmpty()) {
			Pair node = toVisit.remove();
			long nodeDist = node.f;
			int nodeIdx = node.s;
			// si el nodo ya está visitado, lo ignoramos
			if (dist[nodeIdx] != nodeDist) continue;
 
			// child: f: costo, s: nodo hijo
			for (Pair child : adj.get(nodeIdx)) {
				long cost = child.f;
				int childNode = child.s;
				num[childNode] %= MOD;
				// si se halla un camino más corto, reiniciar num, maxf y minf del hijo
				if (cost + dist[nodeIdx] < dist[childNode]) {
					dist[childNode] = cost + dist[nodeIdx];
					num[childNode] = num[nodeIdx];
					maxf[childNode] = maxf[nodeIdx] + 1;
					minf[childNode] = minf[nodeIdx] + 1;
					toVisit.add(new Pair(dist[childNode], childNode));
					// con distancia equivalente, actualizar num, maxf y minf
				} else if (cost + dist[nodeIdx] == dist[childNode]) {
					num[childNode] += num[nodeIdx];
					maxf[childNode] = Integer.max(maxf[childNode], maxf[nodeIdx] + 1);
					minf[childNode] = Integer.min(minf[childNode], minf[nodeIdx] + 1);
				}
			}
		}
 
		num[n - 1] %= MOD;
		out.println(String.format("%d %d %d %d", dist[n - 1], num[n - 1], minf[n - 1],
		                          maxf[n - 1]));
		out.close();
	}
 
	private static class Pair implements Comparable<Pair> {
		long f;
		int s;
 
		public Pair(long x, int y) {
			f = x;
			s = y;
		}
 
		@Override
		public int compareTo(Pair o) {
			int dx = Long.compare(f, o.f);
			if (dx == 0) return s - o.s;
			else return dx;
		}
	}
}