#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct str{
    int nod,cost;
    bool operator<(const str &other) const{
        return cost>other.cost;
    }
};
priority_queue <str> co;
vector <str> v[50003];
int n,m,cst[10000];
int main()
{
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=0;i<=n;i++)
    {
        cst[i]=100000;
    }
    co.push({1,0});
    cst[1]=0;
    while(!co.empty())
    {
        int z=co.top().nod;
        int cc=co.top().cost;
        co.pop();
        for(int i=0;i<v[z].size();i++)
        {
            if(cst[v[z][i].nod]>cst[z]+v[z][i].cost)
            {
                cst[v[z][i].nod]=cst[z]+v[z][i].cost;
                co.push({v[z][i].nod,cst[v[z][i].nod]});
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        g<<cst[i]<<" ";
    }

    return 0;
}