#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,X,Y,Z;
struct pct
{
    int x,y;
};
vector<pct>a[50005];
int dist[50005];
struct comp
{
    bool operator()(const pct &X, const pct &Y)
    {
        return X.y<Y.y;
    }
};
priority_queue<pct,vector<pct>,comp>q;
void dijkstra()
{
    q.push({1,0});
    for(int i=2;i<=n;i++)
        dist[i]=1e9;
    while(!q.empty())
    {
        pct X=q.top();
        q.pop();
        if(X.y!=dist[X.x])
            continue;
        for(auto it : a[X.x])
        {
            if(dist[it.x]>it.y+X.y)
            {
                dist[it.x]=it.y+X.y;
                q.push({it.x,dist[it.x]});
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>X>>Y>>Z;
        a[X].push_back({Y,Z});
    }
    dijkstra();
    for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
    return 0;
}