WASHINGTON [—] The nation’s passport headaches may be easing a bit, but now comes the bill: almost $1 billion.

New travel rules that swamped passport offices and frustrated U.S. travelers this summer will cost the government an estimated $944 million over three years, according to federal paperwork filed Wednesday.

That amount is more than three times the State Department’s estimate for the first three years.

To raise the extra dollars, the department wants to keep a larger share of what U.S. citizens pay to get a passport [—] $20 of the nearly $100 fee for first-time applicants instead of $6.

Kurtis Cooper, a State Department spokesman, said the new proposal will not increase the cost of passports to the public.

The department initially figured it would cost $289 million between budget years 2006 and 2008 to handle the boost in demand for passports created by post-Sept. 11, 2001, security measures passed by Congress and implemented by the Homeland Security Department.

Now, the passport rules are expected to cost $944 million in budget years 2008 to 2010.

This year’s surge in passport applications stems from new rules that went into effect in January requiring U.S. travelers to carry passports when flying to Canada, Mexico and the Caribbean. A similar requirement is to go into effect for all land and sea crossings next year.