import [Link].
*;
import [Link].*;
class Main {
static final int MAX = 2000; // Maximum number of nodes
static long[][] dist = new long[MAX][MAX]; // Distance
matrix for shortest paths
static long[][] dist2 = new long[MAX][MAX]; // Another
distance matrix for modified paths
static boolean[] removed = new boolean[MAX]; // Indicates
if an edge is removed
static int n, m; // Number of nodes and edges
// Class to represent an edge in the graph
static class Edge {
int u, v, cost, num;
Edge(int u, int v, int cost, int num) {
this.u = u;
this.v = v;
[Link] = cost;
[Link] = num;
}
}
// Class to represent a node in the graph
static class Node implements Comparable<Node> {
int id, dist, num;
Node(int id, int dist, int num) {
[Link] = id;
[Link] = dist;
[Link] = num;
}
@Override
public int compareTo(Node other) {
return [Link]([Link], [Link]);
}
}
// Adjacency list representation of the graph
static List<Node>[] graph = new ArrayList[MAX];
// Dijkstra's algorithm for finding shortest paths
static void dijkstra(int node) {
PriorityQueue<Node> q = new PriorityQueue<>();
[Link](new Node(node, 0, 0));
while (![Link]()) {
Node cur = [Link]();
for (Node next : graph[[Link]]) {
int adj = [Link], w = [Link], num =
[Link];
// Relaxation step
// If the distance from the current node to
the adjacent node is greater than
// the sum of the distance from the current
node to itself and the weight of the edge between
// the current node and the adjacent node,
then update the distance from the source node to the
// adjacent node with the new shorter
distance.
if (dist[node][adj] > dist[node][[Link]] + w)
{
dist[node][adj] = dist[node][[Link]] + w;
// Update the distance
[Link](new Node(adj, (int) dist[node][adj],
0)); // Add the adjacent node to the priority queue
}
}
}
}
// Modified Dijkstra's algorithm considering removed edges
static void dijkstra2(int node, int no_use) {
PriorityQueue<Node> q = new PriorityQueue<>();
[Link](new Node(node, 0, 0));
while (![Link]()) {
Node cur = [Link]();
for (Node next : graph[[Link]]) {
int adj = [Link], w = [Link], num =
[Link];
// Skip removed edges
if (num == no_use || removed[num]) continue;
// Relaxation step
if (dist2[node][adj] > dist2[node][[Link]] +
w) {
dist2[node][adj] = dist2[node][[Link]] +
w;
[Link](new Node(adj, (int) dist2[node]
[adj], 0));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
n = [Link](); // Number of nodes
m = [Link](); // Number of edges
// Initializing adjacency list
for (int i = 0; i < MAX; i++) {
graph[i] = new ArrayList<>();
}
List<Edge> edges = new ArrayList<>(); // List to store
edges
long cost = 0; // Total cost of all edges
[Link](removed, false); // Initially, no edge is
removed
// Input edges and build the graph
for (int i = 1; i <= m; i++) {
int u = [Link](), v = [Link](), l =
[Link](), c = [Link]();
graph[u].add(new Node(v, l, i));
graph[v].add(new Node(u, l, i));
[Link](new Edge(u, v, c, i));
cost += c; // Accumulate the cost
}
// Initialize distance matrices
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = Long.MAX_VALUE;
dist2[i][j] = Long.MAX_VALUE;
}
}
// Run Dijkstra's algorithm for each node to find
shortest paths
for (int i = 1; i <= n; i++) {
dist[i][i] = 0;
dijkstra(i);
}
// Sort edges by cost
[Link]([Link](e -> [Link]));
// Process edges in increasing order of cost
for (Edge e : edges) {
int u = e.u, w = [Link], num = [Link];
dist2[u][u] = 0; // Initialize the distance from u
to u
dijkstra2(u, num); // Run modified Dijkstra's
algorithm
int co = 0; // Counter for checking if all nodes
are reachable
for (int i = 1; i <= n; i++) {
if (dist[u][i] == dist2[u][i]) {
co++; // Increment counter if reachable
through both paths
}
}
// If all nodes are reachable through the shortest
path,
// update the cost and mark the edge as removed
if (co == n) {
cost -= w;
removed[num] = true;
}
// Reset distances for the next iteration
for (int i = 1; i <= n; i++) {
dist2[u][i] = Long.MAX_VALUE;
}
}
// Output the minimum cost
[Link](cost);
}
}