#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
using PII = pair<int,int>;
using VI = vector<int>;
const int Inf=0x3f3f3f3f;
int N,M;
vector<vector<PII>> G;
VI d;
void Read();
void Dijkstra(int x, VI& d);
int main(){
    Read();
    Dijkstra(1,d);
    for(int i=2;i<=N;++i)
    if(d[i]!=Inf)
fout<<d[i]<<" ";
else fout<<0<<" ";
fout.close();
}
void Read()
{
fin>>N>>M;
G=vector<vector<PII>>(N+1);
while(M--)
{
int x,y,c;
fin>>x>>y>>c;
G[x].push_back({y,c});
}
fin.close();
}
void Dijkstra(int x, VI& d)
{
priority_queue<PII, vector<PII>, greater<PII>> Q;
d[x]=0;
Q.push({0,x});
while(!Q.empty())
{
int x_nou=Q.top().second, dx=Q.top().first;
Q.pop();
if(d[x_nou]<dx) continue;
for(auto p : G[x_nou])
{
int y=p.first, w=p.second;
if(d[y]>d[x_nou]+w)
d[y]=d[x_nou]+w;
Q.push({d[y],y});
}}}