ST. PAUL, Minn. — The Minnesota Supreme Court said Friday that Gov. Mark Dayton’s veto of the Legislature’s budget was constitutional and ordered the two sides into mediation, a setback for Republican legislative leaders in their legal fight with the Democratic governor.

The high court’s order gives Dayton and legislative leaders until Tuesday to hire a mediator to work out their differences to secure permanent funding for the Legislature — or else the court would find one for them.

Delivered late Friday afternoon, the Supreme Court’s was nuanced. It said Dayton’s action was constitutional, yet didn’t explicitly reverse a lower court’s decision that nullified the governor’s line-item veto as an unconstitutional violation of the separation of powers.

Instead, the high court hoped the two sides could reach a verdict through court-ordered mediation, shying away from the months-long legal battle between the branches of government that stems from the messy end of the legislative session this spring.

Noting the questions surrounding the Legislature’s ability to run without its $130 million operating budget, the court left it to lawmakers themselves to find an answer, saying “the other branches should resolve these doubts through the political process.”

The Democratic governor welcomed Friday’s order, saying it preserved the executive branch’s line-item veto authority and hoping that the two sides could reach an agreement through mediation.

“I remain ready and very willing to engage in those negotiations immediately. I have asked my legal team to contact their legislative counterparts to begin to resolve this matter,” Dayton said.

House Speaker Kurt Daudt and Senate Majority Leader Paul Gazelka, in a joint statement, said they were ready for mediation. But they also seized on a portion of the high court’s order as supportive of their side.

“While we do not dispute the governor’s line-item veto authority, the court order also recognized that “Constitutional powers may not be used ‘to accomplish an unconstitutional result,'” they said.

It’s the latest stage in a months-long legal battle between the branches of government that stemmed from the messy end of the legislative session this spring.

Dayton used his line-item veto to remove the Legislature’s $130 million budget in May. He hoped to pressure lawmakers back to St. Paul to slim down a $650 million tax bill he signed and remove other provisions such as a rulemaking ban on issuing driver’s licenses to immigrants living in the state illegally.

But the Legislature sued, and won, in district court. The Democratic governor appealed that lower court’s ruling that his veto unconstitutional, putting the case on a Supreme Court fast track.

Dayton had appointed four of seven justices on the Supreme Court bench, and one of the three Republican appointees, Justice David Stras, recused himself from the case.

Dayton’s attorney argued his actions were legal, saying the governor’s options to rework objectionable measures were limited and arguing Minnesota’s constitution places no limits on line-item vetoes. But an attorney for the Legislature called it a blatant violation of the separation of powers, and one that could unleash future governors if the Supreme Court didn’t uphold a July ruling from Ramsey County Judge John Guthmann.

Guthmann nullified Dayton’s veto and restored the Legislature’s funding, saying that Dayton essentially eliminated “a branch of government and refashioned the line-item veto tool to secure the repeal or modification of policy legislation unrelated to the vetoed appropriation.”

Taxpayers will foot both sides of the legal dispute, and it won’t be cheap. The Dayton administration had paid $245,000 in legal fees through August, according to Minnesota Management and Budget Commissioner Myron Frans. The Legislature’s agreement with Kelley, Wolter and Scott calls for one lump payment after the case concludes.