#include <fstream>
#include <vector>
#include <queue>
#define infinit 2e9

using namespace std;

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


int n,m;

struct noduri{
    int nod,cost;
};

vector<noduri>V[50001];
priority_queue<noduri>heap;

int dp[50001];
bool viz[50001];

inline bool operator<(noduri x,noduri y){
    return x.cost>y.cost;
}

int main()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        V[x].push_back({y,c});
    }

    //dj
    int cnod=1;
    for(int i=1;i<=n;i++)
        dp[i]=infinit;
    dp[cnod]=0;
    viz[cnod]=1;
    heap.push({cnod,0});
    while(!heap.empty())
    {
        cnod=heap.top().nod;
        heap.pop();
        viz[cnod]=0;
        for(auto &it:V[cnod])
            if(dp[it.nod]>dp[cnod]+it.cost)
            {
                dp[it.nod]=dp[cnod]+it.cost;
                if(!viz[it.nod])
                {
                    viz[it.nod]=1;
                    heap.push({it.nod,dp[it.nod]});
                }
            }

    }
    for(int i=2;i<=n;i++)
        fout<<dp[i]<<' ';
    return 0;
}