#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int NMAX=5e4+5, INF=1e9;
int n, m, dist[NMAX], viz[NMAX];
struct edge
{
    int v, c;
    friend bool operator<(const edge a, const edge b)
    {
        return a.c>b.c;
    }
};
vector<edge> adj[NMAX];
priority_queue<edge> pq;

void Dijkstra()
{
    pq.push({1, 0});
    while(!pq.empty())
    {
        edge u=pq.top(); pq.pop();
        if(viz[u.v])
            continue;
        viz[u.v]=1;
        for(auto e:adj[u.v])
            if(!viz[e.v] && u.c+e.c<=dist[e.v])
            {
                dist[e.v]=u.c+e.c;
                pq.push({e.v, dist[e.v]});
            }
    }
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
    }
    for(int i=2;i<=n;i++)
        dist[i]=INF;
    Dijkstra();
    for(int i=2;i<=n;i++)
        cout<<((dist[i]==INF)?0:dist[i])<<" ";
    return 0;
}