bellman struct

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
typedef  struct
{
  int u,v,w;
}node;
ll n,m;
const ll MAX = 1e5+7 , inf=INFINITY;
vector<node>adj;
long long dis[MAX];
void bellman_ford(int s)
{
      for(ll i=1;i<=n;i++)
      {
         dis[i]=inf;
      }

      for(ll i=1;i<n;i++)
      {
        for(node  x:adj)
        {
            ll u=x.u;
            ll v=x.v;
            ll w=x.w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
            }
        }
      }

}
int main()
{

    cin>>n>>m;

    for(ll i=1; i<=m; i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;

       node a;

       a.u=u;
       a.v=v;
       a.w=w;
       adj.push_back(a);

    }

    bellman_ford(0);

    for(ll i=0;i<n;i++)
    {
        cout<<i<<" "<<dis[i]<<endl;
    }


    return 0;
}
/*

3 3
0 1 1000
1 2 15
2 1 -42


*/