c495

#include".\template\headers.hpp"

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}

struct node {int b; ll w; node(int x, ll y): b(x), w(y) {}};
bool operator<(node a, node b) {
    return a.w > b.w;
}
bool operator==(node a, node b) {
    return a.b == b.b && a.w == b.w;
}

inline void solve() {
    int n, m;
    cin >> n >> m;
    V<V<node>> edge(n), mst(n);
    while (m--) {
        static ll a, b, w;
        cin >> a >> b >> w, a--, b--;
        edge[a].emplace_back(b, w);
        edge[b].emplace_back(a, w);
    }
    V<ll> d(n, 1e15);
    V<int> p(n, -1);
    V<bool> vis(n, false);
    PQ<node> pq;
    pq.emplace(0, p[0] = d[0] = 0);
    for (int k = 0; k < n; k++) {
        static int a; a = ~0u;
        while (pq.size() && vis[a = pq.top().b]) pq.pop();
        if (!~a) break;
        vis[a] = true;
        for (const auto& i : edge[a])
            if (!vis[i.b] && i.w < d[i.b])
                pq.emplace(i.b, d[i.b] = i.w), p[i.b] = a;
    }
    ll mstp = accumulate(d.begin(), d.end(), 0ll);
    cout << mstp << ' ';
    for (int i = 1; i < n; i++) {
        mst[p[i]].emplace_back(i, d[i]);
        static int a, b, w;
        a = p[i], b = i, w = d[i];
        edge[a].erase(find(edge[a].begin(), edge[a].end(), node(b, w)));
        edge[b].erase(find(edge[b].begin(), edge[b].end(), node(a, w)));
    }
    V<V<node>> v(n, V<node>(__lg(n), {0, 0}));
    V<int> tin(n), tout(n);
    F<void(int, int, int)> build = [&](int cur, int pre, ll wt) {
        static int t = 0;
        tin[cur] = t++;
        for (int i = 0, k = pre; i < __lg(n); i++) {
            v[cur][i].b = k, v[cur][i].w = max(v[cur][i].w, wt);
            k = v[k][i].b, wt = v[k][i].w;
        }
        for (const auto& i : mst[cur])
            if (i.b != pre) build(i.b, cur, i.w);
        tout[cur] = t++;
    };
    auto isanc = [&](int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    };
    auto query = [&](int a, int b) {
        if (isanc(a, b)) return a;
        if (isanc(b, a)) return b;
        for (int i = __lg(n) - 1; i >= 0; i--)
            if (!isanc(v[a][i].b, b)) a = v[a][i].b;
        return v[a][0].b;
    };
    auto maxp = [&](int a, int b) {
        int anc = query(a, b);
        ll ret = 0;
        for (int i = __lg(n) - 1; i >= 0; i--) {
            if (!isanc(v[a][i].b, anc)) ret = max(ret, v[a][i].w), a = v[a][i].b;
            if (!isanc(v[b][i].b, anc)) ret = max(ret, v[b][i].w), b = v[b][i].b;
        }
        return ret;
    };
    build(0, 0, 0);
    ll diff = 1e18;
    for (int a = 0; a < n; a++)
        for (const auto& i : edge[a])
            diff = min(diff, i.w - maxp(a, i.b));
    cout << mstp + diff << endl;
}

main() {
    ios::sync_with_stdio(false);
    init();
    int t = 1;
#ifdef MULTI_TASKCASE
    cin >> t; cin.ignore();
#endif
    while (t--) solve();
    return 0;
}