<Dijkstra> TEMPLATE

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define pb push_back
#define mp make_pair

#define f first
#define s second

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) FOR(i, 0, a)

const int MAX = 100005;
const int MOD = 1000000007;
const int MAGIC = 3;

vi g[MAX];
int e1[MAX], e2[MAX], w[MAX];
int d[MAX];
int main() {
    F0R(i, MAX) { d[i] = MOD; }
    int n, m; scanf("%d %d", &n, &m);
    F0R(i, m) {
        int u, v, wt; scanf("%d %d %d", &u, &v, &wt);
        e1[i] = u; e2[i] = v; w[i] = wt;
        g[u].pb(i); g[v].pb(i);
    }
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({0, s});
    while (!pq.empty()) {
        pii tp = pq.top(); pq.pop();
        int dist = tp.f; int u = tp.s;
        if (dist > d[u]) { continue; }
        for (int i : g[u]) {
            int v = e1[i] + e2[i] - u;
            int dv = dist + w[i];
            if (dv < d[v]) { d[v] = dv; pq.push({d[v], v}); }
        }
    }
}