Faits:
A.
B.A._ et A.A._ se sont mariés en décembre 2007. Séparés depuis juin 2014, ils ont deux enfants: C._, né en mars 2006, et D._, né en août 2013.
A.A._ est également le père de E._, né en juin 2021.
B.
A.A._ a déposé une requête unilatérale en divorce le 18 octobre 2016 devant la juge du district de Monthey.
Le divorce a été prononcé le 21 septembre 2018; seule la contribution d'entretien du père en faveur des enfants communs demeure actuellement litigieuse, étant précisé que leur garde est attribuée à la mère.
B.a. Vu la situation financière de A.A._ - alors provisoirement à l'étranger et sans revenu - la juge de district a dans un premier temps renoncé à l'astreindre au versement d'une contribution d'entretien. Dès le 30 avril 2019, elle l'a astreint au versement d'une contribution d'entretien de 200 fr. par mois pour chacun des enfants, sous réserve d'indexation.
B.b. B.A._ a appelé de cette décision, réclamant, à titre de mesures provisoires, le versement d'une contribution d'entretien de 500 fr. par mois et par enfant, allocations familiales en sus, avec effet rétroactif au 1er janvier 2018; elle a réclamé le même montant au fond.
Statuant à titre provisionnel le 14 mai 2019, le juge délégué a notamment porté le montant de la contribution d'entretien à 500 fr. par mois à compter du 1er juin 2019; par décision du 22 février 2021, il a rejeté la requête de A.A._ visant à réduire le montant de la contribution.
Par jugement du 31 août 2021, la Cour civile II du Tribunal cantonal du Valais a réformé la décision de première instance en ce sens que A.A._ versera une contribution à l'entretien de chacun de ses enfants de 600 fr. par mois, sous réserve d'indexation.
C.
Agissant le 1er octobre 2021 par la voie du recours en matière civile au Tribunal fédéral, A.A._ (ci-après: le recourant) conclut principalement à ce que la contribution destinée à l'entretien de C._ et D._ soit arrêtée à 350 fr. par mois chacun, à ce qu'il ne doit aucun dépens à sa partie adverse, leurs frais judiciaires étant répartis entre elles à part égale; à titre subsidiaire, il réclame l'annulation de l'arrêt déféré et le renvoi de la cause à l'autorité cantonale pour nouvelle décision. Le recourant sollicite le bénéfice de l'assistance judiciaire.
Des déterminations n'ont pas été demandées.

Considérant en droit :
1.
Les conditions de recevabilité du recours en matière civile sont ici réalisées (art. 72 al. 1, art. 74 al. 1 let. b avec l'art. 51 al. 1 let. a et al. 4; art. 75 al. 1 et 2, art. 76 al. 1 let. a et b, art. 90 et art. 100 al. 1 LTF).
2.
2.1. Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Cela étant, eu égard à l'exigence de motivation contenue à l'<ref-law>, il n'examine en principe que les griefs soulevés (<ref-ruling> consid. 2.4). Le recourant doit par conséquent discuter les motifs de la décision entreprise et indiquer précisément en quoi l'autorité précédente a méconnu le droit (<ref-ruling> consid. 1.7.1; <ref-ruling> consid. 2.4). Le Tribunal fédéral ne connaît par ailleurs de la violation de droits fondamentaux que si un tel grief a été expressément invoqué et motivé de façon claire et détaillée (" principe d'allégation ", <ref-law>; <ref-ruling> consid. 2.1; <ref-ruling> consid. 2; <ref-ruling> consid. 2.4).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 1.3.1). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte, c'est-à-dire arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.2; <ref-ruling> consid. 5.2.2; <ref-ruling> consid. 2.3), doit, sous peine d'irrecevabilité, satisfaire au principe d'allégation susmentionné (<ref-law>; cf. supra consid. 2.1.1; <ref-ruling> consid. 2.2; <ref-ruling> consid. 1.3.1).
En matière d'appréciation des preuves et d'établissement des faits, il y a arbitraire lorsque l'autorité ne prend pas en compte, sans aucune raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 4.2; <ref-ruling> consid. 1.1; <ref-ruling> consid. 2.3).
3.
Le recourant s'en prend d'abord à différents postes de ses charges incompressibles.
3.1. Il reproche à l'autorité cantonale de ne pas avoir tenu compte dans celles-ci des frais relatifs à l'exercice de son droit de visite.
Vu la situation financière des parties, l'arrêt entrepris a arrêté les contributions d'entretien en se fondant sur les besoins incompressibles des parents et des enfants. N'en font pas partie les frais qu'entraîne l'exercice du droit de visite pour le parent qui n'a pas la garde des enfants; ces frais sont en revanche pris en compte lorsque le minimum vital du droit de la famille sert de base de calcul à l'entretien convenable (<ref-ruling> consid. 7.2). Dans cette mesure, l'exercice effectif du droit de visite n'est pas déterminant, au contraire de ce que paraît penser le recourant. Sa critique est ainsi infondée.
3.2. Le recourant prétend ensuite que, pour ses frais de repas hors domicile, c'est la somme de 11 fr., usuellement accordée, qui aurait dû être retenue par l'autorité cantonale.
Celle-ci a pris en considération un montant de 10 fr. par repas, lequel entre parfaitement dans la moyenne des chiffres indiqués par les lignes directrices pour le calcul du minimum vital du droit des poursuites selon l'article 93 LP, à savoir une fourchette située entre 9 et 11 fr. par repas principal. La critique du recourant ne peut ainsi qu'être écartée.
3.3. Le recourant s'en prend encore au calcul de ses frais professionnels. Il reproche d'abord à la cour cantonale de ne pas avoir appliqué le forfait fiscal de 0,70 centime (sic!) par kilomètre destiné à l'amortissement de son véhicule, relevant qu'un montant, au minimum 65 centimes, lui était pourtant nécessaire à ce titre, son véhicule étant déjà très usagé; il soutient également que la cour cantonale aurait calculé de manière erronée la distance qu'il parcourait pour se rendre à son travail, celle-ci atteignant 25,8 km. En définitive, ce serait ainsi un montant de 631 fr. 55 qu'il faudrait retenir chaque mois pour ses frais de déplacement (25,8 km x 2 x 0,65 cts/km [sic!] x 18,83 jours).
3.3.1. Pour arrêter les frais de transport, la cour cantonale s'est référée à la méthode appliquée par le tribunal cantonal fribourgeois. Celle-ci consiste à multiplier le nombre de kilomètres aller-retour jusqu'au lieu de travail, le nombre de trajets par semaine et le prix de l'essence, montant auquel l'on ajoute un forfait entre 100 fr. et 300 fr. couvrant l'entretien, l'assurance et l'impôt sur le véhicule. L'autorité cantonale a en revanche refusé de tenir compte d'un montant de 70 centimes par kilomètre, respectivement 65 centimes comme le réclame actuellement le recourant, destiné à l'amortissement du véhicule; celui-ci n'avait en effet pas à être pris en considération pour le calcul du minimum vital. Le recourant ne critique pas cette dernière motivation, pourtant appuyée par la jurisprudence (arrêt 5A_508/2011 du 21 novembre 2011 consid. 4.2.3 et la référence), se limitant à insister sur le caractère particulièrement usagé de son véhicule pour se voir attribuer une marge d'amortissement. L'on soulignera par ailleurs que le kilométrage de sa voiture a été pris en considération par la cour cantonale dans l'attribution du montant forfaitaire mensuel de 200 fr.
3.3.2. S'agissant du nombre de kilomètres séparant le domicile du recourant de son lieu de travail, la cour cantonale s'est fondée sur une distance U._ − V._ de 25 km. Le recourant estime celle-ci à 25,8 km, arguant qu'il doit rejoindre l'autoroute sur les hauts de la ville. Aucun élément n'appuie toutefois cette légère différence kilométrique, laquelle conduit de surcroît à une différence de coûts de 4 fr. 50 par mois. L'on relèvera au demeurant que la distance fixée par la cour cantonale apparaît correspondre à celle qui ressort du site de calculateur d'itinéraire en ligne viamichelin, en sorte qu'elle n'est de toute manière pas arbitraire.
3.3.3. Il n'y a pas lieu d'entrer en matière sur les critiques subsidiaires développées par le recourant selon lesquelles la consommation de 0.08 litre par kilomètre et le prix de l'essence retenus par la cour cantonale étaient trop bas: leur caractère général et abstrait ne permet de procéder à aucun calcul concret.
4.
Le recourant critique ensuite les charges de ses enfants, singulièrement le montant retenu à titre de part au loyer de leur mère.
4.1. S'agissant d'abord du montant même du loyer, le recourant part de la prémisse erronée que l'intimée vivrait en concubinage. Cette affirmation, déjà formulée devant les juges cantonaux, a cependant été écartée par ceux-ci, sans que le recourant le conteste.
4.2. Sans à juste titre remettre en cause le principe de la prise en compte d'une participation aux frais de logement du parent gardien dans les frais d'entretien des enfants (<ref-ruling> consid. 7.2), le recourant prétend que c'est un pourcentage de 10% pour chacun d'eux qui aurait dû être retenu et non une participation de 15% comme admis par la cour cantonale en référence à la jurisprudence. Cette affirmation, que le recourant appuie exclusivement sur le fait que les enfants seraient au nombre de deux, ne permet manifestement pas de retenir que le tribunal cantonal aurait outrepassé le pouvoir d'appréciation dont il dispose à cet égard (arrêt 5A_1065/2020 du 2 décembre 2021 consid. 4.2.3 et la référence); cette appréciation reste d'ailleurs parfaitement dans les limites généralement admises par la jurisprudence (cf. arrêts 5A_952/2019 du 2 décembre 2020 consid. 5.3.3.3 [admission implicite d'un pourcentage de 20% pour deux enfant]; 5A_583/2018 du 18 janvier 2019 consid. 3.2 [admission implicite d'un pourcentage de 15% pour deux enfants également]).
5.
Dans un dernier grief, le recourant reproche à la cour cantonale d'avoir arbitrairement omis de fixer l'entretien de son troisième enfant, en se limitant à retenir que le montant de ses besoins serait moindre que ceux de ses frères aînés. En tant que sa compagne actuelle devait contribuer à la moitié des frais communs, elle devrait nécessairement travailler et placer leur enfant. Or il était notoire que, dans le canton de Vaud, les frais de garderie ou de crèche privée se situaient entre 80 et 120 fr. la journée, circonstance dont le recourant déduit que les coûts à sa charge pour cet enfant seraient de l'ordre de 1'145 fr. par mois.
5.1. Le tribunal cantonal a ici retenu qu'une fois ses besoins incompressibles couverts - contestés sans succès ( supra consid. 3) -, le recourant bénéficiait d'un solde de 1'852 fr. 75. Selon les juges cantonaux, ce montant lui permettait de contribuer à l'entretien de ses deux fils aînés à hauteur de 600 fr. chacun - montant inférieur à leurs coûts directs, critiqués sans succès également (consid. 4 supra) -, de même qu'à celui de leur demi-frère, né au mois de juin 2021 et dont les besoins, en l'état, étaient moindres.
5.2. L'on ignore certes sur quelle base factuelle la cour cantonale arrive à cette dernière conclusion, faute de toute indication concernant les coûts actuels, voire prévisibles, du troisième enfant du recourant. Il n'en demeure pas moins que, devant la Cour de céans, le recourant ne démontre pas qu'une fois acquittées les contributions d'entretien en faveur de ses fils aînés, le montant de 650 fr. qui reste à sa disposition serait insuffisant pour assurer l'entretien de son troisième enfant. A défaut de tout caractère prétendument notoire, les frais de garde qu'il invoque, fondés du reste sur un placement hypothétique de l'enfant en crèche, ne reposent sur aucun moyen de preuve tangible: à l'évidence, un simple tirage internet apparaît en effet insuffisant pour les illustrer concrètement.
Faute de toute démonstration de l'insuffisance des moyens à disposition pour assurer les coûts d'entretien de son troisième enfant, le recourant n'est pas fondé à invoquer le principe de l'égalité de traitement entre les bénéficiaires de l'entretien.
6.
Vu l'issue du recours, il n'y a pas lieu de revoir la répartition des frais et dépens décidée par l'instance cantonale, ainsi que le souhaite le recourant.
7.
En définitive, le recours doit être rejeté dans la mesure où il est recevable. La requête d'assistance judiciaire du recourant est rejetée, ses conclusions étant d'emblée vouées à l'échec. Les frais judiciaires sont ainsi mis à sa charge (<ref-law>). Aucune indemnité de dépens n'est accordée à l'intimée qui n'a pas été invitée à se déterminer.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La requête d'assistance judiciaire du recourant est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour civile II.
Lausanne, le 18 mars 2022
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : Herrmann
La Greffière : de Poret Bortolaso