#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int nmax = 5e4, inf=1e9;
int n, m;
vector <pair<int, int>> graph[nmax+1];
vector <int> d(nmax+1, inf);
priority_queue <pair<int, int>> q;
bitset <nmax> vis;
void dijkstra()
{
    q.push({0, 1});
    d[1]=0;
    while(!q.empty())
    {
        int nod=q.top().second;
        q.pop();
        //if(vis[nod]==0)
        //{
            for(int i=0; i<graph[nod].size(); i++)
            {
                int copil = graph[nod][i].first, dist = graph[nod][i].second;
                if(d[nod]+dist<d[copil] && vis[copil]==0)
                {
                    d[copil]=d[nod]+dist;
                    vis[copil]=1;
                    q.push({-d[copil], copil});
                }
            }
            //vis[nod]=1;
        //}
    }
}
int main()
{
    int a, b, c;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>a>>b>>c;
        graph[a].push_back({b, c});
    }
    dijkstra();
    for(int i=2; i<=n; i++)
    {
        if(d[i]==inf)
            out<<0<<" ";
        else
            out<<d[i]<<" ";
    }
}