The first issue of Charlie Hebdo after jihadists executed most of its journalists was sold out within hours across France on Wednesday, as Al-Qaeda issued a video claiming last week's attack.

The satirical magazine once again featured the Prophet Mohammed on its cover -- but with a tear in his eye, holding a "Je Suis Charlie" sign under the headline "All is forgiven".

Many Parisians joined long queues outside newspaper kiosks in the pre-dawn cold to get their hands on one of 700,000 copies of the first run that will eventually total five million.

"This issue is symbolic, it represents their persistance, they didn't yield in the face of terror," said Catherine Boniface, a 58-year-old doctor, disappointed to have come up empty-handed at one Paris newstand.

Distributors quickly announced the print run would be increased from an initial three million -- dwarfing Charlie Hebdo's normal run of around 60,000 copies, and the edition will also be available in English, Spanish, Italian, Arabic and Turkish.

Al-Qaeda's Yemen branch (AQAP) claimed responsibility for the attack by Islamist gunmen on the magazine last Wednesday that left 12 people dead including the country's best-loved cartoonists.

"(AQAP) was the party that chose the target and plotted and financed the plan... It was following orders by our general chief Ayman al-Zawahiri," said one of its leaders in the video, adding it was "vengeance" for the weekly's cartoons of the prophet.

Brothers Said and Cherif Kouachi who carried out the attack are known to have trained with the group.

Amedy Coulibaly, who killed a policewoman and attacked a Jewish supermarket, has claimed links to the Islamic State group in Syria and Iraq, which on Wednesday described Charlie Hebdo's decision to print another Mohammed cartoon as "extremely stupid".

Some global Muslim leaders have criticised the new cartoon, with the Qatar-based International Union of Muslim Scholars saying "it is neither reasonable, nor logical, nor wise to publish drawings and films... attacking the prophet of Islam."

But many have taken a nuanced stance and tried to calm tensions, with French Muslim leaders urging their communities -- which have already been targeted -- to "stay calm and avoid emotive reactions".

War on terrorism

Despite the outpouring of support for free speech in recent days, its limits were exposed on Wednesday when controversial comedian Dieudonne Mbala Mbala was arrested for condoning terrorism by writing "I feel like Charlie Coulibaly" on Facebook.

He was mixing the popular slogan "Je Suis Charlie" used in homage to the slain journalists with a reference to the supermarket gunman.

The justice ministry said over 50 cases have been opened for "condoning terrorism" since the three days of terror that claimed 17 lives.

Charlie Hebdo's surviving staff moved into the offices of Liberation newspaper to compile the new issue, which they admitted had been an emotional experience.

Cartoonist Renald "Luz" Luzier said he cried after drawing the front cover.

"Our Mohammed is above all just a guy who is crying. He is much nicer than the one (worshipped) by the gunmen," he said.

French Prime Minister Manuel Valls said Tuesday the country was now engaged in a "war on terrorism", in remarks reminiscent of former US president George W. Bush's declaration of war against terrorists after the 9/11 attacks in 2001.

But Valls stressed that Muslims would always have a home in France.

"I don't want Jews in this country to be scared, or Muslims to be ashamed" of their faith, he said.

He admitted France's intelligence capabilities and anti-terrorism laws needed to be strengthened and "clear failings" addressed.

The three gunmen were known to French intelligence and on a US terror watch list "for years".

On Tuesday, President Francois Hollande led a solemn ceremony paying tribute to the three police officers killed, while the Jewish victims were also buried in Israel.

"France will never break, will never yield, never bend" in the face of the Islamist threat that is "still there, inside and outside" the country, he said.

Symbol of free speech

Charlie Hebdo, which lampoons everyone from the president to the pope, has become a symbol of freedom of expression in the wake of the bloodshed.

Proceeds from the new edition will go to victims' families.

A version will be published in predominantly Muslim Turkey as an inset in the centre-left opposition daily Cumhuriyet, one of the paper's journalists said.

Underlining the ongoing security worries, France's biggest satirical weekly, "Le Canard Enchaine", said it received a death threat the day after the Charlie Hebdo attack.

France has deployed armed police to protect synagogues and Jewish schools and called up 10,000 troops to guard against other attacks.

US Secretary of State John Kerry will meet Hollande on Friday to discuss the attacks. The United States did not send a senior official to the historic march against extremism on Sunday, which the White House has admitted was a mistake.