#include <bits/stdc++.h>
#define MOD 2e9
#define NMAX 50500
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m, x,y,c,dist[NMAX];
bool use[NMAX];
vector<pair<int,int>> v[NMAX];
set<pair<int,int>> q;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({c,y});
    }

    dist[1]=0;
    for(int i=2;i<=n;++i)
        dist[i]=MOD;

    q.insert({0,1});
    while(q.empty()==false)
    {
        y=q.begin()->first;
        x=q.begin()->second;
        q.erase(q.begin());
        use[x]=1;

        if(y==dist[x])
            for(auto i:v[x])
                if(use[i.second]==0)
                {
                    dist[i.second]=min(dist[i.second],y+i.first);
                    q.insert({dist[i.second],i.second});
                }
    }

    for(int i=2;i<=n;++i)
        fout<<dist[i]<<" ";

    return 0;
}