#include <fstream>
#include<vector>
#include<set>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf=0x3f3f3f3f;
struct nod
{
    int vecin,cost;
    bool operator < (const nod &other) const
    {
        if(cost!=other.cost)
            return cost<other.cost;
        return vecin<other.vecin;
    }
};
vector<nod>G[50005];
vector<int>dmin;
set<nod>S;
int n,m;
void dijkstra(int st)
{
    dmin=vector<int>(n+1,inf);
    dmin[st]=0;S.insert({st,0});
    while(!S.empty())
    {
        int nd=S.begin()->vecin;
        S.erase(S.begin());
        for(auto&i:G[nd])
        {
            int costpos=i.cost+dmin[nd];
            if(costpos<dmin[i.vecin])
            {
                if(dmin[i.vecin]!=inf)S.erase({i.vecin,dmin[i.vecin]});
                S.insert({i.vecin,costpos});
                dmin[i.vecin]=costpos;
            }
        }
    }
}

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

    for(int i=2;i<=n;i++)
        if(dmin[i]==inf)cout<<0<<" ";
    else cout<<dmin[i]<<" ";
    return 0;
}