#include <bits/stdc++.h>

namespace IO {
	template <class Stream>
	Stream& fmtbase(Stream& out, const char* format) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				throw std::invalid_argument("Error Number of Parameters!");
			}
			
			out << *format;
		}
		
		return out;
	}
	
	template <class Stream, class Fst, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				out << value;
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}
	
	template <class... Ps>
	std::string to_string(const char* format, const Ps&... ps) {
		std::stringstream ss;
		fmtbase(ss, format, ps...);
		return ss.str();
	}

	template <class... Ps>
	std::ostream& fmtout(const char* format, const Ps&... ps) {
		return fmtbase(std::cout, format, ps...);
	}
	
	template <class... Ps>
	std::ostream& fmterr(const char* format, const Ps&... ps) {
		return fmtbase(std::cerr, format, ps...);
	}
	
	std::istream& allin() {
		return std::cin;
	}
	
	template <class Fst, class ... Nxt>
	std::istream& allin(Fst& fst, Nxt&... nxt) {
		std::cin >> fst;
		return allin(nxt...);
	}
	
	template <class Iter>
	std::istream& rangin(Iter begin, Iter end) {
		while (begin != end) {
			std::cin >> *begin;
			begin++;
		}
		
		return std::cin;
	}
	
	namespace Fast {
		bool sync = false;
		
		char buf[1 << 23];
		char *p1 = buf, *p2 = buf;
		
		void sync_with_ios(bool s) {
			sync = s;
		}
		
		char getchar() {
			if (sync) {
				return (char) std::cin.get();
			}
			else {
				if (p1 == p2) {
					p1 = buf;
					p2 = p1 + fread(buf, 1, 1 << 22, stdin);
				}
				
				if (p1 == p2) {
					return EOF;
				}
				else {
					char res = *p1;
					p1++;
					return res;
				}
			}
		}
		
		void read() { }
		
		template <class T, class... U>
		void read(T& x, U&... us) {
			x = 0;
			T pos = 1;
			
			char c = getchar();
			while (!isdigit(c)) {
				if (c == '-') {
					pos = -1;
				}
				
				c = getchar();
			}
			
			while (isdigit(c)) {
				x = 10 * x + c - '0';
				c = getchar();
			}
			
			x *= pos;
			read(us...);
		}
		
		template <class T>
		void write(const T& t) {
			if (t > 10) {
				write(t / 10);
			}
			
			std::cout << (int) (t % 10);
		}
	}
}

namespace Solve {
	#define int long long

	using namespace IO;

	using ll = long long;
	using ul = unsigned long long;
	using db = double;
	using ld = long double;
	using ui = unsigned;
	using ib = __int128;
	using ub = __uint128_t;

	int const INF = std::numeric_limits<int>::max();
	int const NINF = std::numeric_limits<int>::min();
	ll const LINF = std::numeric_limits<ll>::max();
	ll const LNINF = std::numeric_limits<ll>::min();
	ld const EPS = 1e-6;

	std::mt19937 mt;

	ll rnd(ll l, ll r) {
		return std::uniform_int_distribution<ll>(l, r)(mt);
	}

	template <class T>
	inline int isz(const T& v) {
		return v.size();
	}

	template <class T>
	inline T& ckmx(T& a, T b) {
		return a < b ? (a = b) : a;
	}

	template <class T>
	inline T& ckmi(T& a, T b) {
		return b < a ? (a = b) : a;
	}

	template <signed M>
	struct ModInt {
		static signed const MOD = M;

		ui v;

		ModInt() : v(0) {}

		ModInt(ll v) {
			if (-MOD <= v && v < 2 * MOD) {
				if (v >= MOD) {
					v -= MOD;
				}
			}
			else {
				v %= MOD;
			}
			if (v < 0) {
				v += MOD;
			}
			this->v = v;
		}

		ModInt operator++(signed) {
			auto t = *this;
			v = v == MOD - 1 ? 0 : v + 1;
			return t;
		}
		
		ModInt& operator++() {
			v = v == MOD - 1 ? 0 : v + 1;
			return *this;
		}
		
		ModInt operator--(signed) {
			auto t = *this;
			v = v == 0 ? MOD - 1 : v - 1;
			return t;
		}

		ModInt& operator--() {
			v = v == 0 ? MOD - 1 : v - 1;
			return *this;	
		}

		ModInt& operator+=(ModInt rhs) {
			v = v + rhs.v >= MOD ? v + rhs.v - MOD : v + rhs.v;
			return *this;
		}

		ModInt& operator-=(ModInt rhs) {
			v = v >= rhs.v ? v - rhs.v : v + MOD - rhs.v;
			return *this;
		}

		ModInt& operator*=(ModInt rhs) {
			v = (ul) v * rhs.v % MOD;
			return *this;
		}

		static void exgcd(signed a, signed b, signed& x, signed& y) {
			if (!b) {
				x = 1, y = 0;
				return;
			}

			signed t = a / b;
			exgcd(b, a - t * b, y, x);
			y -= t * x;
		}

		ModInt inv() const {
			assert(v != 0);

			signed x, y;
			exgcd(v, MOD, x, y);
			if (x < 0) {
				x += MOD;
			}			
			return x;
		}

		ModInt& operator/=(ModInt rhs) {
			return operator*=(rhs.inv());
		}

		ModInt fpow(ll b) const {
			assert(b >= 0);
			ModInt ans = 1;
			ModInt p = *this;
			while (b) {
				if (b & 1) {
					ans *= p;
				}
				p *= p;
				b >>= 1;
			}
			return ans;
		}

		friend bool operator==(ModInt a, ModInt b) {
			return a.v == b.v;
		}

		friend bool operator!=(ModInt a, ModInt b) {
			return a.v != b.v;
		}

		friend ModInt operator+(ModInt a, ModInt b) {
			return a += b;
		}

		friend ModInt operator-(ModInt a, ModInt b) {
			return a -= b;
		}

		friend ModInt operator*(ModInt a, ModInt b) {
			return a *= b;
		}

		friend ModInt operator/(ModInt a, ModInt b) {
			return a /= b;
		}

		friend ModInt operator-(ModInt a) {
			return 0 - a;
		}
	};

	template <signed MOD>
	std::istream& operator>>(std::istream& in, ModInt<MOD>& mint) {
		ll v;
		in >> v;
		mint = ModInt<MOD>(v);
		
		return in;
	}

	template <signed MOD>
	std::ostream& operator<<(std::ostream& out, ModInt<MOD> mint) {
		return out << mint.v;
	}

	template <class T, int B>
	struct FastPow {
		T baby[B + 1];
		T gaint[B + 1];
		
		FastPow(T b) {
			baby[0] = 1;
			for (int i = 1; i <= B; i++) {
				baby[i] = baby[i - 1] * b;
			}
			
			gaint[0] = 1;
			for (int i = 1; i <= B; i++) {
				gaint[i] = gaint[i - 1] * baby[B];
			}
		}
		
		T get(int n) {
			return gaint[n / B] * baby[n % B];
		}
	};

	int const MOD = 998244353;

	template <signed M>
	const signed ModInt<M>::MOD;

	using Mint = ModInt<MOD>;

	int const N = 2e5 + 10;

	struct Group {
		int d, x;
	};

	struct Edge {
		int u, v, w;
	};

	int n, a, b;
	std::vector<int> ds[N + 1];
	Group gs[N + 1];
	std::vector<Edge> eds;
	Mint ans;
	std::map<int, int> fa;

	int get(int x) {
		return fa[x] == x ? x : fa[x] = get(fa[x]);
	}

	int grt(int n, std::vector<int> d, int v) {
		while (true) {
			int mi = -1;
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && (mi == -1 || d[i] < d[mi])) {
					mi = i;
				}
			}
			if (mi == -1 || n <= d[mi]) {
				return v;
			}

			int c = n / d[mi];
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					ckmi(c, d[i] / d[mi]);
				}
			}

			n -= d[mi] * c;
			if (v >= n) {
				v -= ((v - n) / d[mi] + 1) * d[mi];
				if (n < d[mi] && v < 0) {
					v += d[mi];
					return v;
				}
			}

			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					d[i] -= c * d[mi];
				}
			}
		}
	}

	void grt_all(int n, std::vector<int> d, std::vector<int>& v) {
		std::vector<int> done(isz(v));
		while (true) {
			int mi = -1;
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && (mi == -1 || d[i] < d[mi])) {
					mi = i;
				}
			}
			if (mi == -1 || n <= d[mi]) {
				return;
			}

			int c = n / d[mi];
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					ckmi(c, d[i] / d[mi]);
				}
			}

			n -= d[mi] * c;
			for (int i = 0; i < isz(v); i++) {
				if (done[i]) {
					continue;
				}
				if (v[i] >= n) {
					v[i] -= ((v[i] - n) / d[mi] + 1) * d[mi];
					if (n < d[mi] && v[i] < 0) {
						v[i] += d[mi];
						done[i] = 1;
					}
				}
			}

			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					d[i] -= c * d[mi];
				}
			}
		}
	}

	Mint count(int n, std::vector<int> d) {
		Mint ans;
		while (true) {
			int mi = -1;
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && (mi == -1 || d[i] < d[mi])) {
					mi = i;
				}
			}
			if (mi == -1 || n <= d[mi]) {
				ans += n;
				break;
			}

			int c = n / d[mi];
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					ckmi(c, d[i] / d[mi]);
				}
			}

			n -= d[mi] * c;
			if (n < d[mi]) {
				ans += d[mi] - n;
			}

			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					d[i] -= c * d[mi];
				}
			}			
		}
		return ans;
	}

	std::vector<int> mark(int n, std::vector<int> d) {
		std::vector<int> ans, od;
		od = d;
		while (true) {
			int mi = -1;
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && (mi == -1 || d[i] < d[mi])) {
					mi = i;
				}
			}
			if (mi == -1 || n <= d[mi]) {
				break;
			}

			ans.push_back(od[mi]);

			int c = n / d[mi];
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					ckmi(c, d[i] / d[mi]);
				}
			}

			n -= d[mi] * c;
			for (int i = 0; i < isz(d); i++) {
				if (d[i] && i != mi) {
					d[i] -= c * d[mi];
				}
			}			
		}

		ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
		return ans;
	}

	namespace Sub1 {
		void main() {
			std::sort(gs + 1, gs + a + 1, [&](const Group& a, const Group& b) {
				return a.x < b.x;
			});

			Mint lst = n;
			for (int i = 1; i <= a; i++) {
				auto d = ds[i - 1];
				d.push_back(gs[i].d);
				auto cur = count(n, d);
				ans += (lst - cur) * gs[i].x;
				ds[i] = mark(n, d);
				lst = cur;
			}
		}
	}

	namespace Sub2 {
		void solve(int l, int r, std::vector<int> vs) {
			if (l > r || isz(vs) <= 1) {
				return;
			}

			std::vector<int> ps = vs;
			int mid = (l + r) >> 1;
			grt_all(n, ds[mid], ps);
			std::map<int, std::vector<int>> mp;
			for (int i = 0; i < isz(vs); i++) {
				mp[ps[i]].push_back(vs[i]);
			}

			if (l == r) {
				for (auto& pr : mp) {
					for (int i = 0; i + 1 < isz(pr.second); i++) {
						eds.push_back({ pr.second[i], pr.second[i + 1], gs[l].x });
						ans -= gs[l].x;
					}
				}
				return;
			}

			for (auto& pr : mp) {
				solve(l, mid, pr.second);
			}

			std::vector<int> vv;
			for (auto& pr : mp) {
				vv.push_back(pr.second[0]);
			}
			solve(mid + 1, r, vv);
		}

		void main() {
			for (auto& v : eds) {
				fa[v.u] = v.u;
				fa[v.v] = v.v;
			}

			std::vector<int> vv;
			for (auto& v : eds) {
				vv.push_back(v.u);
				vv.push_back(v.v);
			}
			std::sort(vv.begin(), vv.end());
			vv.erase(std::unique(vv.begin(), vv.end()), vv.end());
			solve(1, a, vv);

			std::sort(eds.begin(), eds.end(), [&](const Edge& a, const Edge& b) {
				return a.w < b.w;
			});
			for (auto& e : eds) {
				// fmterr("? {} {} {}\n", e.u, e.v, e.w);
				if (get(e.u) != get(e.v)) {
					ans += e.w;
					fa[get(e.u)] = get(e.v);
				}
			}
		}
	}

	void main() {
		std::cin >> n >> a >> b;fmtout("{}\n", (n-1)%MOD);
return;


		for (int i = 1; i <= a; i++) {
			int d, x;
			std::cin >> d >> x;
			gs[i] = { d, x };
		}

		for (int i = 1; i <= b; i++) {
			int x, y, w;
			std::cin >> x >> y >> w;
			eds.push_back({ x, y, w });
		}

		Sub1::main();
		Sub2::main();

		fmtout("{}\n", ans);
	}

	void init() {

	}

	void clear() {

	}
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int t = 1;
	// std::cin >> t;

	Solve::init();
	
	for (int id = 1; id <= t; id++) {
		Solve::main();
		Solve::clear();
	}

	return 0;
}