#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
bool inside(ll i, ll j, ll r, ll c)
{
  return (i < r && j < c && i >= 0 && j >= 0);
}
 
pair<ll, ll> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
 
void solve()
{
  ll n ; 
  cin>>n;
 
  ll m ;
  cin>>m ;
 
  vector<pair<ll , ll >>adj[n+1];
 
 
  for(ll i = 0  ; i< m ; i++)
  {
    ll a, b , c ;
    cin>>a>>b>>c ;
 
    adj[a].push_back({b ,c});
    // adj[b].push_back({a,c});
 
  }
 
  vector<ll> dist(n + 1, LLONG_MAX);
  // vector<bool>vis(n+1, false);
 
  priority_queue<pair<ll ,ll >  , vector<pair< ll , ll > >  , greater<pair<ll ,ll >> > q ;
 
  q.push({0 , 1});
  dist[1] = 0 ;
 
  while(q.empty()==false)
  {
    auto u = q.top();
    q.pop();
 
    for(auto x:  adj[u.second])
    {
      // cout<<dist[x[0]]<<" "<<dist[u.first]<<" "<<x[1]<<endl;
 
        if(dist[x.first] > dist[u.second] + x.second)
        {
          dist[x.first] = dist[u.second] + x.second;
          q.push({dist[x.first], x.first});
        }
    }
  }
 
  for(ll i =1 ; i<=n  ; i++)
  cout<<dist[i]<<" ";
  cout<<endl;
 
} 
 
 
 
int main()
{
 
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
 
  ull t = 1;
  // cin >> t;
  // cout << "nooml";
  while (t--)
  {
    solve();
  }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
bool inside(ll i, ll j, ll r, ll c)
{
  return (i < r && j < c && i >= 0 && j >= 0);
}
 
pair<ll, ll> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
void solve()
{
  int n, m;
  cin >> n >> m;
 
  vector<vector<char>> arr(n, vector<char>(m, '#'));
 
  int s1 = -1, s2 = -1;
 
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      cin >> arr[i][j];
      if (arr[i][j] == 'A')
      {
        s1 = i;
        s2 = j;
      }
    }
 
  vector<vector<bool>> vis(n, vector<bool>(m, false));
 
  map<pair<int, int>, char> hash;
 
  hash[{0, 1}] = 'R';
  hash[{1, 0}] = 'D';
  hash[{0, -1}] = 'L';
  hash[{-1, 0}] = 'U';
 
  queue<pair<pair<int, int> , string> > q;
 
  // cout<<s1<<" "<<s2<<endl<<endl;
  q.push({{s1, s2} , ""});
 
  vis[s1][s2]= true ;
 
  while (q.empty() == false)
  {
    auto u = q.front();
    q.pop();
 
    for (auto p : directions)
    {
      int x = p.first + u.first.first;
      int y = p.second + u.first.second;
 
      if (inside(x, y, n, m)  && vis[x][y] ==false && (arr[x][y] == '.' || arr[x][y] == 'B'))
      {
 
        string str = u.second;
        str += hash[{p.first, p.second}];
 
        // cout<<x<<":"<<y<<endl;
        if (arr[x][y] == 'B')
        {
          cout << "YES" << endl;
          cout << str.length() << endl;
          cout << str << endl;
          return;
        }
        // cout << x << ":" << y << endl;
        vis[x][y] = true;
        q.push({{x, y} , str});
      }
    }
  }
 
  cout << "NO" << endl;
}
int main()
{
 
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
 
  ull t = 1;
  // cin >> t;
  // cout << "nooml";
  while (t--)
  {
    solve();
  }
}

...

int not_take = fun(n-1 , val)
int take = fun(n ,val - arr[n])

int not_take = fun(n-1 , val)
int take = fun(n ,val - arr[n] ) + fun(n-1 , val- arr[n])

#include <bits/stdc++.h>

using namespace std;

/*
 * Complete the 'xorAndSum' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING a
 *  2. STRING b
 */
 
 
unsigned long long int convert(string s)
{
    reverse(s.begin(), s.end());
    
    unsigned long long int ans = 0;
    unsigned long long int n = s.length();
    
    unsigned long long int mul =1 ;
    for(unsigned long long int i = 0 ; i<n; i++)
    {
        ans+=mul*(s[i]=='1');
        mul*=2;
    }
    
    return ans ;
}

unsigned long long int xorAndSum(string a, string b) {
    
    unsigned long long int mod = 1000000007;
    unsigned long long int a1 = convert(a);
    unsigned long long int b1 = convert(b);
    long long int ans  =0 ;


    for(int i =0  ; i <=314159  ; i++)
    {
        
        unsigned long long int bn = (b1<<i)%mod;
        
        ans = (ans + (a1^bn)%mod)%mod;
        
        
    }
    

    return ans ;
    
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string a;
    getline(cin, a);

    string b;
    getline(cin, b);

     long long int result = xorAndSum(a, b);

    fout << result << "\n";

    fout.close();

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

/*
 * Complete the 'steadyGene' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING gene as parameter.
 */

int steadyGene(string gene) {

int n =gene.length();
int req = n/4;

map<char, int >hash ;

hash['A']=0;
hash['C']=0;
hash['G']=0;
hash['T']=0;
for(auto x: gene)
hash[x]++;

int ctr = 0 ;

map<char ,int >miss;

int l = 0 ,  r= 0;

int ans = n ; 


for(auto x: hash)
{
    ctr+=max(0 , req-x.second);
    miss[x.first] = max(0 , req-x.second);
}

if(ctr==0)
return 0 ;

map<char, int >win;

for(int i = l ; i<=r ;i++)
win[gene[i]]++;

string check="ACGT";
int m =0 ;

while(r<n)
{
    int places=0;

    for(auto x: check)
    {
        if(miss[x]==0)
        places+=win[x];
    }
    
        
        while(places>=ctr && l<=r)
        {
            
            if(places>=ctr)
            ans = min(ans , r-l+1);
        
            win[gene[l]]--;
            l++;
             places=0;
            
            for(auto x: check)
            {
                if(miss[x]==0)
                places+=win[x];
            }
            

        }
        
    
    r++;
    win[gene[r]]++;
}

return ans ;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string n_temp;
    getline(cin, n_temp);

    int n = stoi(ltrim(rtrim(n_temp)));

    string gene;
    getline(cin, gene);

    int result = steadyGene(gene);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}