// this code doesnt work unless you comment the lines 71-73 part...

// proof:
/*
input
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 1000
1

then input
5 5
1 5 1000
1 2 1
2 3 1
3 4 1
4 5 1
1

if you un-comment the lines, both output differently.
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define endl '\n'

#define MOD 1000000007

ll mod(ll a) {
    return (a%MOD + MOD)%MOD;
}

ll binpow(ll x, ll n) {
    if (n == 0) {
        return 1;
    }
    if (x == 0) {
        return 0;
    }
    if (n%2 == 0) {
        ll temp = binpow(x,n/2);
        return mod(temp*temp);
    }
    return mod(mod(x)*binpow(x,n-1));
}

void print(bool& ans) { cout << (ans ? "YES" : "NO") << endl; }

// now we have weights(positive). Had weights were negative, we couldnot have used it.

#define f first
#define s second

vector<vector<pair<ll,ll>>> adj;
vector<ll> vis, dis;

void sssp(int src) {
    dis[src] = 0;
    queue<ll> q;
    q.push(src);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // if (vis[node]) {    // the code works when you comment this part, because now for every time a node is pushed, it checks for distance.
        //     continue;
        // }
        vis[node] = 1;

        for (auto &x:adj[node]) {
            if (dis[x.f] > dis[node] + x.s) {
                dis[x.f] = dis[node] + x.s;
                q.push(x.f);
            }
        }
    }
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    adj = vector<vector<pair<ll,ll>>> (n+1);
    vis = vector<ll> (n+1,0);
    dis = vector<ll> (n+1,1e9);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }

    int src;
    cin >> src;
    sssp(src);
    for (int i = 1; i <= n; i++) {
        cout << i << ": " << dis[i] << endl;
    }
    
    return 0;
}

WHAT IS THE TIME COMPLEXITY OF THIS APPROACH? IS THIS BETTER THAN OTHER SSSP ALGORITHMS?