#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> mu;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
bool inq[50004];
int cost[50004],n,m,x,y,c;
const int inf=0x3f3f3f3f;
vector<mu>g[50004];
struct comp
{
    bool operator()(int x,int y)
    {
        return cost[x]>cost[y];
    }
};
priority_queue<int,vector<int>,comp>q;
void dijkstra(int nodS)
{
    int nc,v;
    q.push(nodS);
    cost[nodS]=0;
    inq[nodS]=true;
    while(!q.empty())
    {
        nc=q.top();
        q.pop();
        inq[nc]=false;
        for(unsigned int i=0;i<g[nc].size();i++)
        {
            v=g[nc][i].first;
            c=g[nc][i].second;
            if(cost[v]>cost[nc]+c)
            {
                cost[v]=cost[nc]+c;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=100;i++)
        cost[i]=inf;
    while(m--)
    {
        fin>>x>>y>>c;
        g[x].push_back({y,c});
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        if(cost[i]!=inf)
            fout<<cost[i]<<' ';
        else
            fout<<0<<' ';
    return 0;
}