#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 1000000007

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int>> graph[50001];
int dist[50001];

//class cmp
//{
//    public :
//        bool operator()(int x,int y)
//        {
//            return dist[x] > dist[y];
//        }
//};

bool cmp(int x,int y)
{
    return dist[x] > dist[y];
}
int main()
{
    int n,m;
    fin >> n >> m;
    while(m--)
    {
        int a,b,c;
        fin >> a >> b >> c;
        graph[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
    {
        dist[i]=INT_MAX;
    }
    vector<int> Q;
    //priority_queue<int, vector<int>, cmp> Q;
    Q.push_back(1);
    dist[1]=0;
    while(!Q.empty())
    {
        int node = Q[0];
        pop_heap(Q.begin(),Q.end(),cmp);
        Q.pop_back();
        for(auto i : graph[node])
        {
            if(dist[i.first] > dist[node]+i.second)
            {
                dist[i.first]=dist[node]+i.second;
                Q.push_back(i.first);
                push_heap(Q.begin(),Q.end(),cmp);
            }
        }
    }

    for(int i=2;i<=n;i++)
    {
        if(dist[i]!=INT_MAX)
        {
            fout << dist[i] << " ";
        }
        else
        {
            fout << 0 << " ";
        }
    }
}