#include <bits/stdc++.h>

using namespace std;

#define INF 10000000000
vector < pair <int, int> > G[50001];
priority_queue <pair <int, int>, vector <pair <int, int> > ,greater <pair <int,int> > > Q;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,dist[50001],p=1;
bool viz[50001];
void read()
{
    int i,a,b,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        G[a].push_back({c,b});


    }
}
void init()
{
    int i;
    Q.push({0,p});
    for(i=1;i<=n;i++)
        dist[i]=INF,viz[i]=0;
dist[p]=0;
}
void Dijkstra()
{
    int node,cost;
    while(!Q.empty())
    {
        node=Q.top().second;
cost=Q.top().first;
Q.pop();
        if(viz[node]!=1)
        {
            viz[node]=1;


            for( auto x: G[node])
            if(x.first+cost<dist[x.second]) { Q.push(make_pair(x.first+dist[node],x.second));
            dist[x.second]=x.first+cost;
            }
        }


    }
}

int main()
{
    read();
    init();
    Dijkstra();
    for(int i=2; i<=n;i++)
        if(dist[i]==INF) g<<0<<" "; else g<<dist[i]<<" ";

}