# HackerRank Minimum MST Graph problem solution

In this HackerRank Minimum MST Graph problem solution you have Given n, m, and s for g graphs satisfying the conditions above, find and print the minimum sum of the lengths of all the edges in each graph on a new line.

## Problem solution in Python.

```g = int(input().strip())
for a0 in range(g):
n, m, s = map(int, input().strip().split(' '))
n2 = (n * n - 3 * n + 4) // 2
if n == 2:
print(s)
else:
if m <= n2:
print(s + m - n + 1)
else:
a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
x = n - 1 - s % (n - 1)
y = s % (n - 1)
div = s // (n - 1)
t = (x * (x + 1)) // 2
a2 = t * div
a2 += max(0, (div + 1) * (m - t))
rem = s - (n - 2) * div
kant = ((n - 2) * (n - 1)) // 2
a3 = kant * div + (m - kant) * rem
print(min(a1, a2, a3))
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

private static long minimumWeight(long n, long m, long s) {
if (m <= (n - 1)*(n - 2)/2 + 1) {
return m + s - n + 1;
} else {
long core = (n - 1)*(n - 2)/2;
long unbalanced = core + (s - n + 2)*(m - core);

long base = s/(n - 1);
long larger = s - base*(n - 1);
long smaller = n - 1 - larger;

long midbalanced = base*core + (base + larger)*(m - core);

long balanced;
if (larger > 0) {
core = smaller*(smaller + 1)/2;
balanced = base*core + (base + 1)*(m - core);
} else {
balanced = base*m;
}

return Math.min(Math.min(unbalanced, balanced), midbalanced);
}
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) {
int g = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int gItr = 0; gItr < g; gItr++) {
String[] nms = scanner.nextLine().split(" ");

int n = Integer.parseInt(nms[0]);

long m = Long.parseLong(nms[1]);

long s = Long.parseLong(nms[2]);

System.out.println(String.format("%d", minimumWeight(n, m, s)));
}

scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <iostream>

using namespace std;

int main() {
long long n, m, s;
cin >> n >> m >> s;
long long ans = 0;
if ((n - 1) * (n - 2) / 2 + 1 >= m) {
ans = s + m - n + 1;
} else {
if (-(n-2) * (m - (n - 1) * (n - 2)/2) + (n - 2) * (n - 1) / 2 < 0) {
//average
long long k = s / (n - 1);
long long t = s % (n - 1);
ans = (m - (n - 1) * (n - 2) / 2) * (s - (n - 2) * k) + (n - 2) * (n - 1) / 2 * k;
if (t != 0) {
ans = min(ans,
(k + 1) * (m - (n - 1) * (n - 2) / 2) + (n - 1) * (n - 2) / 2 * k + (t - 1) * (2 * n - t - 2) / 2
);
}
} else {
ans = (m - (n - 1) * (n - 2) / 2) * (s - n + 2) + (n - 2) * (n - 1) / 2;
}
}
cout << ans << endl;
}
return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
//using namespace std;
typedef long long ll;
ll min(ll a,ll b)
{
if(a>b)
return b;
else
return a;
}
void run()
{
ll N, M, S;
scanf("%lld%lld%lld",&N,&M,&S);
//cin >> N >> M >> S;
ll blen = S - (N - 2);
ll nedge = ((N - 1) * (N - 2)) / 2;
ll ans=0;
if (M > nedge)
{
ll bremain = M - nedge;
if ((N - 1) * bremain < M)
{
ans = nedge + (M - nedge) * blen;
}
else
{
ll cval = S - (N - 1);
ans = M + (M * (cval / (N - 1)));
cval %= N - 1;
ll lval = cval * bremain;
ll rval = 1e18;
if (cval)
{
rval = bremain + (cval - 1) * (N - 2) - (cval - 1) * (cval - 2) / 2;
}
ans += min (lval, rval);
}
}
else
{
ans = (M - 1) + blen;
}
printf("%lld\n",ans);
// cout << ans << "\n";
}
int main()
{
int ntest,test;
scanf("%d",&ntest);
// cin >> ntest;
for (test = 0; test < ntest; test++)
run();
}
```

{"mode":"full","isActive":false}