CSES - Shared codeLink to this code: https://cses.fi/paste/56b942b47666376d7be871/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fst first
#define snd second

int inf=1e15;
int n,m;
vector<int>dist;
vector<pair<pii,int>>aristas;
vector<vector<pair<int,int>>>adj;
vector<bool>mark;

bool BellmanFord(int source){
   dist[source]=0;
   for(int i=1;i<n;i++){
      bool flag=false;
      for(int k=0;k<aristas.size();k++){
         int a=aristas[k].fst.fst, b=aristas[k].fst.snd, peso=aristas[k].snd;
         if(dist[b]>dist[a]+peso){
            flag=true;
            dist[b]=dist[a]+peso;
         }
      }
      if(!flag){
         break;
      }
   }

   return true;
}
void BFS(int source){
   queue<int>cola;
   cola.push(source);
   set<pii>mark_edges;
   while(!cola.empty()){
      int nodo=cola.front();
      //cout<<nodo<<" ";
      cola.pop();
      mark[nodo]=true;
      for(int i=0;i<adj[nodo].size();i++){
         pair<pii,int> edge={{nodo,adj[nodo][i].snd},adj[nodo][i].fst};
         if(mark_edges.count(edge.fst)==0){
            mark_edges.insert(edge.fst);
            aristas.pb(edge);
            if(!mark[adj[nodo][i].snd]){
               cola.push(adj[nodo][i].snd);
               mark[adj[nodo][i].snd]=true;
            }
         }
      }
   }

}

signed main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   int t=1;
   while(t--){
      cin>>n>>m;
      dist.assign(n+1,inf);
      adj.assign(n+1,vector<pair<int,int>>());
      mark.assign(n+1,false);
      vector<pair<pii,int>>vec, al_fin;
      for(int i=1;i<=m;i++){
         int x,y,peso;cin>>x>>y>>peso;
         vec.pb({{x,y},peso});
         //aristas.pb({{x,y},peso});
      }
      sort(vec.begin(),vec.end());
      for(int i=0;i<vec.size();i++){
         pair<pii,int>aux=vec[i];
         al_fin.pb(aux);
         while(i<vec.size() && vec[i].fst==aux.fst){
            i++;
         }
         i--;
      }

      for(int i=0;i<al_fin.size();i++){
         adj[al_fin[i].fst.fst].pb({al_fin[i].snd,al_fin[i].fst.snd});
      }

      BFS(1);
      //cout<<aristas.size()<<"\n";
      BellmanFord(1);
      for(int i=1;i<=n;i++){
         cout<<dist[i]<<" ";
      }
      cout<<"\n";
   }
   return 0;
}
/*
5 10
1 2 6
1 4 7
2 4 8
4 5 9
5 1 2
4 3 -3
2 5 -4
5 3 7
2 3 5
3 2 -2
*/